제출 #602048

#제출 시각아이디문제언어결과실행 시간메모리
602048SeDunion사탕 분배 (IOI21_candies)C++17
0 / 100
1994 ms50260 KiB
#include "candies.h" #include<algorithm> #include<iostream> #include <vector> using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; const int N = 1e6 + 123; const ll inf = 1e18; ll tmn[N << 2], tmx[N << 2]; ll p[N << 2]; int n, q; void push(int v, int l, int r) { if (!p[v]) return; tmn[v] += p[v], tmx[v] += p[v]; if (r - l > 1) p[v << 1] += p[v], p[v<<1|1] += p[v]; p[v] = 0; } void upd1(int L, int R, ll val, int l = 0, int r = q + 1, int v = 1) { push(v, l, r); if (L <= l && r <= R) { p[v] += val; push(v, l, r); return; } if (L >= r || l >= R) return; int m = (l + r) >> 1; upd1(L, R, val, l, m, v << 1); upd1(L, R, val, m, r, v<<1|1); tmn[v] = min(tmn[v << 1], tmn[v<<1|1]); tmx[v] = max(tmx[v << 1], tmx[v<<1|1]); } ll gmn1(int L, int R, int l = 0, int r = q + 1, int v = 1) { push(v, l, r); if (L <= l && r <= R) return tmn[v]; if (L >= r || l >= R) return inf; int m = (l + r) >> 1; return min(gmn1(L, R, l, m, v << 1), gmn1(L, R, m, r, v<<1|1)); } ll gmx1(int L, int R, int l = 0, int r = q + 1, int v = 1) { push(v, l, r); if (L <= l && r <= R) return tmx[v]; if (L >= r || l >= R) return -inf; int m = (l + r) >> 1; return max(gmx1(L, R, l, m, v << 1), gmx1(L, R, m, r, v<<1|1)); } void upd(int l, int r, ll val) { upd1(l + 1, r + 1, val); } ll gmn(int l, int r) { return gmn1(l, r + 1); } ll gmx(int l, int r) { return gmx1(l, r + 1); } vector<int>ev[N]; vi distribute_candies(vi c, vi l, vi r, vi v) { n = c.size(); q = l.size(); vector<int>ans; for (int i = 0 ; i < q ; ++ i) ev[l[i]].emplace_back(i), ev[r[i]+1].emplace_back(i); for (int i = 0 ; i < n ; ++ i) { //cout << " ---\n" << i << "\n-\n"; for (int j : ev[i]) { if (l[j] == i) { //cout << "adding " << j << " " << v[j] << endl; upd(j, q, +v[j]); } else { //cout << "deleting " << j << " " << v[j] << endl; upd(j, q, -v[j]); } } int l = 0, r = q - 1; int o = -1; while (l <= r) { int k = (l + r) >> 1; int mx = gmx(k, q), mn = gmn(k, q); //cout << k << " " << mx << " " << mn << endl; if (mx - mn >= c[i]) { l = k + 1; o = k; } else { r = k - 1; } } if (o == -1) { //cout << i << " e\n"; ans.emplace_back(gmx(q, q) - gmn(0, q)); continue; } ll s; if (gmx(o, q) == gmx(o + 1, q)) s = gmx(o + 1, q) - c[i]; else s = gmn(o + 1, q); //cout << i << " " << o << " " << s << endl; ans.emplace_back(gmx(q, q) - s); } return ans; }
#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...