Codeforces 674G Choosing Ads
VK Cup Round 3のボス問。
- 問題概要
区間を埋めるクエリと、区間のうちp%以上を占める数をすべて出力せよというクエリに答えよ。クエリ数, 数の範囲は150000, 20<=p
- 解法
区間のうち1/5以上を占めるものしか出力しなくていいので、区間からランダムに何回か選べば答えの候補は全部列挙できるはず。
よって、ある位置の値を取得するのと区間を埋めるのができれば答えの候補は全部列挙できる。(ただし、前者はたくさんやるのでlogがつかないように平方分割でやる。)
列挙したら、その区間のその数の個数を数える。これも平方分割でできる。このとき、得られたものすべてを見ていると150000のsqrtにさらに何かがかかって大変なので特定個数以上現れたものを出力するなり上から特定番目のものまでを出力するなりすることにする。
これを素直に(ランダムに選ぶ点の数とか実際に個数を数える基準とかのパラメータを適切に調整して)実装するとTLEするので、個数を数えるクエリの定数倍高速化を頑張る。例えば区間の端のブロックを左か右の小さいほうを見るとかをするとバケットサイズも相まって定数倍1/sqrt(2)とかをつけられたりする。
バケットサイズ等のパラメータをいじり、定数倍高速化を頑張ってやっとAC。パラメータをちゃんと考えれば間違える確率は0に収束するから乱択と言っても一応解法の正当性は証明できるけど、これ絶対想定じゃないよね...
Jun/09/2016 16:47 Compilation error [main tests] → 18342397
Jun/09/2016 16:48 Compilation error [main tests] → 18342410
Jun/09/2016 16:49 Compilation error [main tests] → 18342426
Jun/09/2016 16:51 Compilation error [main tests] → 18342466
Jun/09/2016 16:53 Wrong answer on test 24 [main tests] → 18342487
Jun/09/2016 16:54 Wrong answer on test 31 [main tests] → 18342497
Jun/09/2016 16:55 Wrong answer on test 31 [main tests] → 18342514
Jun/09/2016 16:56 Wrong answer on test 31 [main tests] → 18342531
Jun/09/2016 17:00 Wrong answer on test 31 [main tests] → 18342581
Jun/09/2016 17:02 Wrong answer on test 31 [main tests] → 18342614
Jun/09/2016 17:04 Wrong answer on test 31 [main tests] → 18342651
Jun/09/2016 17:08 Wrong answer on test 31 [main tests] → 18342741
Jun/09/2016 18:00 Time limit exceeded on test 50 [main tests] → 18343573
Jun/09/2016 18:01 Time limit exceeded on test 50 [main tests] → 18343586
Jun/09/2016 18:02 Time limit exceeded on test 50 [main tests] → 18343597
Jun/09/2016 18:05 Time limit exceeded on test 50 [main tests] → 18343627
Jun/09/2016 18:06 Time limit exceeded on test 50 [main tests] → 18343649
Jun/09/2016 18:08 Wrong answer on test 43 [main tests] → 18343668
Jun/09/2016 18:09 Time limit exceeded on test 50 [main tests] → 18343681
Jun/09/2016 18:11 Time limit exceeded on test 50 [main tests] → 18343713
Jun/09/2016 18:13 Wrong answer on test 43 [main tests] → 18343741
Jun/09/2016 18:13 Time limit exceeded on test 50 [main tests] → 18343750
Jun/09/2016 18:17 Time limit exceeded on test 48 [main tests] → 18343806
Jun/09/2016 18:18 Time limit exceeded on test 47 [main tests] → 18343818
Jun/09/2016 18:19 Wrong answer on test 44 [main tests] → 18343827
Jun/09/2016 18:20 Time limit exceeded on test 50 [main tests] → 18343839
Jun/09/2016 18:21 Time limit exceeded on test 50 [main tests] → 18343863
Jun/09/2016 18:22 Time limit exceeded on test 50 [main tests] → 18343882
Jun/09/2016 18:24 Wrong answer on test 23 [main tests] → 18343912
Jun/09/2016 18:24 Wrong answer on test 40 [main tests] → 18343919
Jun/09/2016 18:33 Time limit exceeded on test 50 [main tests] → 18344067
Jun/09/2016 18:34 Time limit exceeded on test 50 [main tests] → 18344085
Jun/09/2016 18:34 Time limit exceeded on test 50 [main tests] → 18344097
Jun/09/2016 18:46 Time limit exceeded on test 50 [main tests] → 18344271
Jun/09/2016 18:50 Time limit exceeded on test 50 [main tests] → 18344326
Jun/09/2016 18:51 Time limit exceeded on test 50 [main tests] → 18344340
Jun/09/2016 19:06 Time limit exceeded on test 50 [main tests] → 18344571
Jun/10/2016 16:05 Wrong answer on test 10 [main tests] → 18358899
Jun/10/2016 16:06 Wrong answer on test 71 [main tests] → 18358925
Jun/10/2016 16:10 Wrong answer on test 71 [main tests] → 18358982
Jun/10/2016 16:12 Wrong answer on test 71 [main tests] → 18359017
Jun/10/2016 16:13 Wrong answer on test 71 [main tests] → 18359034
Jun/10/2016 16:14 Wrong answer on test 71 [main tests] → 18359049
Jun/10/2016 16:15 Time limit exceeded on test 1 [main tests] → 18359061
Jun/10/2016 16:17 Accepted [main tests] → 18359095
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; #define SIZE 900 #define NS 167 int now[150400]; int flag[NS]; int dat[NS][150400]; int cnt[150400]; void resolve(int a) { if (flag[a] != -1) { for (int i = 0; i < SIZE; i++) { dat[a][now[a*SIZE + i]] = 0; now[a*SIZE + i] = flag[a]; } dat[a][flag[a]] = SIZE; flag[a] = -1; } } void update(int lb, int ub, int n) { int b1 = lb / SIZE, b2 = ub / SIZE; resolve(b1); resolve(b2); if (b1 == b2) { for (int i = lb; i <= ub; i++) { dat[b1][now[i]]--; now[i] = n; dat[b1][n]++; } } else { for (int i = lb; i < (b1 + 1)*SIZE; i++) { dat[b1][now[i]]--; now[i] = n; dat[b1][n]++; } for (int i = b1 + 1; i < b2; i++) { flag[i] = n; } for (int i = b2*SIZE; i <= ub; i++) { dat[b2][now[i]]--; now[i] = n; dat[b2][n]++; } } } int getv(int p) { if (flag[p / SIZE] != -1)return flag[p / SIZE]; else return now[p]; } int countn(int lb, int ub, int num) { int b1 = lb / SIZE, b2 = ub / SIZE; int ret = 0; if (b1 == b2) { resolve(b1); for (int i = lb; i <= ub; i++) { ret += (now[i] == num); } return ret; } else { if (flag[b1] == -1) { if (lb%SIZE < SIZE / 2) { ret += dat[b1][num]; for (int i = b1*SIZE; i < lb; i++)ret -= (now[i] == num); } else { for (int i = lb; i < (b1 + 1)*SIZE; i++) { ret += (now[i] == num); } } } else if (flag[b1] == num)ret += SIZE - (lb - b1*SIZE); for (int i = b1 + 1; i < b2; i++) { if (flag[i] != -1)ret += SIZE * (flag[i] == num); else ret += dat[i][num]; } if (flag[b2] == -1) { if (ub%SIZE < SIZE / 2) { for (int i = b2*SIZE; i <= ub; i++) { ret += (now[i] == num); } } else { ret += dat[b2][num]; for (int i = ub + 1; i < (b2 + 1)*SIZE; i++)ret -= (now[i] == num); } } else if (flag[b2] == num)ret += ub - b2*SIZE + 1; return ret; } } long long rrr = 2463534242LL; int getrand(int mod) { rrr = (rrr ^ (rrr << 13))&((1LL << 32) - 1); rrr = rrr ^ (rrr >> 17); rrr = (rrr ^ (rrr << 5))&((1LL << 32) - 1); return rrr%mod; } typedef pair<int, int>pii; int main() { int num, query, gen; scanf("%d%d%d", &num, &query, &gen); fill(now, now + 150400, -1); for (int i = 0; i < num; i++) { int z; scanf("%d", &z); z--; now[i] = z; dat[i / SIZE][z]++; } fill(flag, flag + NS, -1); for (int p = 0; p < query; p++) { int z, za, zb; scanf("%d%d%d", &z, &za, &zb); za--; zb--; if (z == 1) { int zc; scanf("%d", &zc); zc--; update(za, zb, zc); } else { int vec[100]; int pt = 0; for (int i = 0; i < 100; i++) { int t = getv(getrand(zb - za + 1) + za); vec[pt++] = t; cnt[t]++; } vector<pii>v; for (int i = 0; i < 100; i++) { if (cnt[vec[i]] >= 3)v.push_back(make_pair(-cnt[vec[i]], vec[i])); cnt[vec[i]] = 0; } sort(v.begin(), v.end()); vector<int>ans; for (int i = 0; i < min(int(v.size()),8); i++) { int t = countn(za, zb, v[i].second); if (t * 100 >= (zb - za + 1)*gen) { ans.push_back(v[i].second); } } printf("%d", ans.size()); for (int i = 0; i < ans.size(); i++)printf(" %d", ans[i] + 1); printf("\n"); } } }
