제출 #446577

#제출 시각아이디문제언어결과실행 시간메모리
446577blue사탕 분배 (IOI21_candies)C++17
100 / 100
1699 ms64336 KiB
#include "candies.h" #include <vector> #include <iostream> using namespace std; const long long INF = 1'000'000'000'000'000'000; struct segtree //min, max, range add { long long l; long long r; long long mn = 0; long long mx = 0; long long lp = 0; segtree* left = NULL; segtree* right = NULL; segtree() { ; } segtree(long long L, long long R) { l = L; r = R; if(l == r) return; long long m = (l+r+10)/2 - 5; left = new segtree(l, m); right = new segtree(m+1, r); } long long rangemin(long long L, long long R) { if(R < l || r < L) return INF; else if(L <= l && r <= R) return mn; else return lp + min(left->rangemin(L, R), right->rangemin(L, R)); } long long rangemax(long long L, long long R) { if(R < l || r < L) return -INF; else if(L <= l && r <= R) return mx; else return lp + max(left->rangemax(L, R), right->rangemax(L, R)); } void add(long long L, long long R, long long V) { if(R < l || r < L) return; // cerr << "adding to " << l << ' ' << r << ": " << L << ' ' << R << ' ' << V << '\n'; if(L <= l && r <= R) { mn += V; mx += V; lp += V; } else { left->add(L, R, V); right->add(L, R, V); mn = lp + min(left->mn, right->mn); mx = lp + max(left->mx, right->mx); } } }; vector<int> distribute_candies(vector<int> c1, vector<int> l1, vector<int> r1, vector<int> v1) { long long N = c1.size(); long long Q = l1.size(); vector<long long> c(N); vector<long long> l(Q), r(Q), v(Q); for(int i = 0; i < N; i++) c[i] = c1[i]; for(int j = 0; j < Q; j++) { l[j] = l1[j]; r[j] = r1[j]; v[j] = v1[j]; } segtree S(-3, Q-1); S.add(-3, -3, -INF); S.add(-2, -2, +INF); vector<long long> insertions[N], removals[N]; for(long long i = 0; i < Q; i++) { insertions[ l[i] ].push_back(i); removals[ r[i] ].push_back(i); } vector<long long> res(N, 0); long long curr_upd_sum = 0; // for(long long j = -1; j <= Q-1; j++) cerr << S.rangemax(j, j) << ' '; // cerr << '\n'; for(long long i = 0; i < N; i++) { // cerr << "i = " << i << '\n'; for(long long o: insertions[i]) { // cerr << "inserting " << o << ": " << l[o] << ' ' << r[o] << ' ' << v[o] << '\n'; S.add(o, Q-1, +v[o]); curr_upd_sum += v[o]; // cerr << "segment tree: "; // for(long long j = -1; j <= Q-1; j++) cerr << S.rangemax(j, j) << ' '; // cerr << '\n'; } long long lower_bound = 0; // cerr << S.rangemax(-1, Q-1) << ' ' << S.rangemin(-1, Q-1) << '\n'; long long last_good = Q-1; // for(last_good = Q-1; last_good >= 0; last_good--) // { // if(S.rangemax(last_good-1, Q-1) - S.rangemin(last_good-1, Q-1) > (long long)c[i]) // break; // } // cerr << "last_good = " << last_good << '\n'; for(long long bit = 19; bit >= 0; bit--) { long long new_good = last_good - (1 << bit); if(new_good < -1) continue; if(S.rangemax(new_good, Q-1) - S.rangemin(new_good, Q-1) <= (long long)c[i]) last_good = new_good; } // cerr << "last_good = " << last_good << '\n'; if(0 <= S.rangemin(0, Q-1) && S.rangemax(0, Q-1) <= c[i]) lower_bound = 0; else if(S.rangemax(last_good-1, last_good-1) < S.rangemax(last_good, last_good)) lower_bound = S.rangemax(last_good, Q-1) - (long long)c[i]; else lower_bound = S.rangemin(last_good, Q-1); // cerr << "curr_upd_sum = " << curr_upd_sum << ", lower_bound = " << lower_bound << '\n'; res[i] = (curr_upd_sum - lower_bound); for(long long o: removals[i]) { // cerr << "removing " << o << '\n'; S.add(o, Q-1, -v[o]); curr_upd_sum -= v[o]; } // cerr << "\n\n"; } vector<int> res1(N); for(int i = 0; i < N; i++) res1[i] = res[i]; return res1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...