Submission #571922

#TimeUsernameProblemLanguageResultExecution timeMemory
571922blueSanta Claus (RMI19_santa)C++17
20 / 100
1098 ms6644 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]]); } } } } // for(int i = N-1; i >= 0; i--) for(int i2 = N; i2 >= maxelf; i2--) { // for(int i2 = i+1; i2 <= N; i2++) // for(int z = i2+1; z <= N; z++) // { if(i2 < N) { if(H[i2+1] == 0) removeelf(V[i2+1]); else if(remgift[i2+1] >= 1) addelf(V[remgift[i2+1]]); } // } 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(H[i+1] == 0) addelf(V[i+1]); else addchild(V[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]); } for(int u = 1; u <= i2; u++) { if(H[u] == 0) { // removeelf(V[u]); // addelf(V[u]); ; } else { removechild(V[u]); if(remgift[u] >= 1) removeelf(V[remgift[u]]); } } } for(int i = 1; i <= N; i++) cout << D[i] << ' '; cout << '\n'; } }

Compilation message (stderr)

santa.cpp: In function 'int main()':
santa.cpp:166:7: warning: unused variable 'jm' [-Wunused-variable]
  166 |   int jm = 0; //J - 1
      |       ^~
#Verdict Execution timeMemoryGrader output
Fetching results...