Submission #571910

#TimeUsernameProblemLanguageResultExecution timeMemory
571910blueSanta Claus (RMI19_santa)C++17
20 / 100
1098 ms12188 KiB
#include <iostream> #include <vector> #include <set> using namespace std; const int mx = 100'000; using vi = vector<int>; using pii = pair<int, int>; struct segtree { vi l = vi((1<<18) + 1); vi r = vi((1<<18) + 1); vi mn = vi((1<<18) + 1, 0); //change to long long if error vi lp = vi((1<<18) + 1, 0); void build(int i, int L, int R) { l[i] = L; r[i] = R; mn[i] = lp[i] = 0; if(l[i] == r[i]) return; int m = (l[i] + r[i])/2; build(2*i, l[i], m); build(2*i+1, m+1, r[i]); } void add(int i, int L, int R, int V) { if(r[i] < L || R < l[i]) return; // cerr << "add " << i << ' ' << l[i] << ' ' << r[i] << " : " << L << ' ' << R << ' ' << V << '\n'; if(L <= l[i] && r[i] <= R) { lp[i] += V; mn[i] += V; } else { add(2*i, L, R, V); add(2*i+1, L, R, V); mn[i] = lp[i] + min(mn[2*i], mn[2*i+1]); } } int rangemin(int i, int L, int R) { // cerr << "rangemin " << i << ' ' << l[i] << ' ' << r[i] << " : " << L << ' ' << R << '\n'; if(r[i] < L || R < l[i]) { // cerr << "case 1\n"; return 1'000'000'000; } else if(L <= l[i] && r[i] <= R) { // cerr << "case 2\n"; return mn[i]; } else { // cerr << "case 3\n"; return lp[i] + min(rangemin(2*i, L, R), rangemin(2*i+1, L, R)); } } }; int N; segtree S; vi X, H, V; multiset<int> elves, children; void output() { for(int i = 0; i <= N; i++) cerr << S.rangemin(1, i, i) << ' '; cerr << '\n'; } void addelf(int i) { cerr << "add elf " << i << '\n'; elves.insert(i); S.add(1, i, N, -1); // output(); } void removeelf(int i) { cerr << "remove elf " << i << '\n'; elves.erase(elves.find(i)); S.add(1, i, N, +1); // output(); } void addchild(int i) { // cerr << "pre : " << S.rangemin(1, 0, 0) << '\n'; cerr << "add child " << i << '\n'; children.insert(i); S.add(1, i, N, +1); // output(); // cerr << "post : " << S.rangemin(1, 0, 0) << '\n'; } void removechild(int i) { cerr << "remove child " << i << '\n'; children.erase(children.find(i)); S.add(1, i, N, -1); // output(); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T; cin >> T; for(int t = 1; t <= T; t++) { cin >> N; S.build(1, 0, N); //could bad values be accessed from previous tests? check if WA // cerr << "pre pre : " << S.rangemin(1, 0, 0) << '\n'; // output(); X = H = V = vi(1+N); int maxelf = 0; for(int i = 1; i <= N; i++) cin >> X[i]; for(int i = 1; i <= N; i++) { cin >> H[i]; if(H[i] == 0) maxelf = max(maxelf, i); } for(int i = 1; i <= N; i++) cin >> V[i]; vi D(1+N, -1); // int jm = 0; //J - 1 set<pii> gifts; // cerr << "Maxelf = " << maxelf << '\n'; vi remgift(1+N, -1); for(int i = 0; i <= N; i++) { // cerr << "i = " << i << '\n'; // cerr << H[i] << '\n'; if(i >= 1) { if(H[i] == 0) //elf { // newgift[i].push_back(i); gifts.insert({V[i], i}); // cerr << "adding elf : " << i << '\n'; addelf(V[i]); } else //child { auto it = gifts.lower_bound({V[i], -1}); if(it != gifts.end()) { remgift[i] = it->second; gifts.erase(it); // cerr << "removing elf : " << remgift[i] << '\n'; removeelf(V[remgift[i]]); } } } } // int jm = N; //last position which is not visited in second phase. // cerr << "done\n"; // for(int i = N; i >= maxelf; i--) // { // if(i+1 <= N) // { // removechild(V[i+1]); // } // while(S.mn[1] < 0 && jm >= 1) // { // if(H[jm] == 0) // removeelf(V[jm]); // else if(remgift[jm] >= 1) // addelf(V[remgift[jm]]); // jm--; // } // if(S.mn[1] >= 0) // D[i] = X[i] + (X[i] - X[jm+1]); // } for(int i = N-1; i >= 0; i--) { if(H[i+1] == 0) removeelf(V[i+1]); else if(remgift[i+1] >= 1) addelf(V[remgift[i+1]]); for(int i2 = i+1; i2 <= N; i2++) { if(H[i2] == 0) addelf(V[i2]); else addchild(V[i2]); if(i2 >= maxelf) if(S.mn[1] >= 0) if(D[i2] == -1 || X[i2] + (X[i2] - X[i+1]) < D[i2]) D[i2] = X[i2] + (X[i2] - X[i+1]); } // cerr << "done\n"; for(int i2 = i+1; i2 <= N; i2++) { if(H[i2] == 0) removeelf(V[i2]); else removechild(V[i2]); } } // for(int i2 = N; i2 >= maxelf; i2--) // { // cerr << "i2 = " << i2 << '\n'; // for(int i = i2-1; i >= 0; i--) // { // if(H[i+1] == 0) // removeelf(V[i+1]); // else if(remgift[i+1] >= 1) // addelf(V[remgift[i+1]]); // if(i2 >= maxelf) // if(S.mn[1] >= 0) // if(D[i2] == -1 || X[i2] + (X[i2] - X[i+1]) < D[i2]) // D[i2] = X[i2] + (X[i2] - X[i+1]); // } // cerr << "hello\n"; // for(int i = i2-1; i >= 0; i--) // { // cerr << i << '\n'; // if(H[i+1] == 0) // { // cerr << "c1\n"; // addelf(V[i+1]); // } // else if(remgift[i+1] >= 1) // { // cerr << "c2\n"; // cerr << i+1 << ' ' << remgift[i+1] << ' ' << V[remgift[i+1]] <<'\n'; // removeelf(V[remgift[i+1]]); // cerr << "removed\n"; // } // cerr << "done\n"; // } // cerr << "world\n"; // if(H[i2] == 0) // removeelf(V[i2]); // else // removechild(V[i2]); // } for(int i = 1; i <= N; i++) cout << D[i] << ' '; cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...