Submission #613781

#TimeUsernameProblemLanguageResultExecution timeMemory
613781Red_InsideDistributing Candies (IOI21_candies)C++17
27 / 100
804 ms34540 KiB
#include "candies.h" // #include <bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back #define mp make_pair #define o cout<<"BUG"<<endl; #define FOR(i, j, n) for(int j = i; j < n; ++j) #define forn(i, j, n) for(int j = i; j <= n; ++j) #define nfor(i, j, n) for(int j = n; j >= i; --j) #define all(v) v.begin(), v.end() #define ld long double #define ull unsigned long long using namespace std; const int maxn=2e5+100,LOG=17,mod=1e9+7; int block = 226, timer = 0; const ld EPS = 1e-18; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define bt(i) (1 << (i)) //#define int ll const int inf=2e9; #define y1 yy #define prev pre #define pii pair <int, int> ll pu[4*maxn]; ll tmx1[4*maxn], tmn1[4*maxn], tmx2[4*maxn], tmn2[4*maxn]; void update(int v) { int v1 = v * 2; int v2 = v * 2 + 1; if(tmx1[v1] > tmx1[v2]) { tmx1[v] = tmx1[v1]; tmx2[v] = max(tmx1[v2], tmx2[v1]); } else if(tmx1[v1] < tmx1[v2]) { tmx1[v] = tmx1[v2]; tmx2[v] = max(tmx2[v2], tmx1[v1]); } else { tmx1[v] = tmx1[v1]; tmx2[v] = max(tmx2[v1], tmx2[v2]); } if(tmn1[v1] < tmn1[v2]) { tmn1[v] = tmn1[v1]; tmn2[v] = min(tmn1[v2], tmn2[v1]); } else if(tmn1[v1] > tmn1[v2]) { tmn1[v] = tmn1[v2]; tmn2[v] = min(tmn1[v1], tmn2[v2]); } else { tmn1[v] = tmn1[v1]; tmn2[v] = min(tmn2[v1], tmn2[v2]); } } void build(int v, int tl, int tr) { if(tl == tr) { tmx1[v] = 0; tmx2[v] = -inf; tmn1[v] = 0; tmn2[v] = inf; return; } build(v * 2, tl, (tl + tr) / 2); build(v * 2 + 1, (tl + tr) / 2 + 1, tr); update(v); } void pushadd(int v, int tl, int tr, ll val) { tmx1[v] += val; if(tmx2[v] != -inf) tmx2[v] += val; tmn1[v] += val; if(tmn2[v] != inf) tmn2[v] += val; pu[v] += val; } void pushmx(int v, int tl, int tr, int val) { if(val <= tmn1[v]) return; tmn1[v] = val; if(tl == tr) tmx1[v] = val; else if(tmx1[v] <= val) { tmx1[v] = val; } else if(tmx2[v] < val) { tmx2[v] = val; } } void pushmn(int v, int tl, int tr, int val) { if(tmx1[v] <= val) return; tmx1[v] = val; if(tl == tr) tmn1[v] = val; else if(tmn1[v] >= val) { tmn1[v] = val; } else if(tmn2[v] > val) { tmn2[v] = val; } } void push(int v, int tl, int tr) { int tm = (tl + tr) / 2; pushadd(v * 2, tl, tm, pu[v]); pushadd(v * 2 + 1, tm+1, tr, pu[v]); pu[v] = 0; pushmx(v * 2, tl, tm, tmn1[v]); pushmx(v * 2 + 1, tm+1, tr, tmn1[v]); pushmn(v * 2, tl, tm, tmx1[v]); pushmn(v * 2 + 1, tm+1, tr, tmx1[v]); } void upd(int v, int tl, int tr, int l, int r, ll val) { if(l > tr || r < tl) return; if(l <= tl && tr <= r) { pushadd(v, tl, tr, val); return; } push(v, tl, tr); upd(v * 2, tl, (tl + tr) / 2, l, r, val); upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, val); update(v); } void updmn(int v, int tl, int tr, int l, int r, int val) { if(l > tr || r < tl || tmx1[v] <= val) return; if(l <= tl && tr <= r && tmx1[v] > val && tmx2[v] <= val) { pushmn(v, tl, tr, val); return; } push(v, tl, tr); updmn(v * 2, tl, (tl + tr) / 2, l, r, val); updmn(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, val); update(v); } void updmx(int v, int tl, int tr, int l, int r, int val) { if(l > tr || r < tl || tmn1[v] >= val) return; if(l <= tl && tr <= r && tmn1[v] < val && tmn2[v] >= val) { pushmx(v, tl, tr, val); return; } push(v, tl, tr); updmx(v * 2, tl, (tl + tr) / 2, l, r, val); updmx(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, val); update(v); } int get(int v, int tl, int tr, int pos) { if(tl == tr) { return tmn1[v]; } push(v, tl, tr); if(pos <= (tl + tr) / 2) return get(v * 2, tl, (tl + tr) / 2, pos); return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos); } vector <int> distribute_candies(vector <int> c, vector <int> l, vector <int> r, vector <int> v) { int n = c.size(); int q = v.size(); vector <int> a; a.assign(n, 0); build(1, 0, n-1); FOR(0, it, q) { upd(1, 0, n-1, l[it], r[it], v[it]); updmn(1, 0, n-1, l[it], r[it], c[0]); updmx(1, 0, n-1, l[it], r[it], 0); /* cout << "AFTER " << it << endl; forn(0, j, n-1) { cout << get(1, 0, n-1, j) << " "; } cout << endl;*/ } forn(0, i, n-1) { a[i] = get(1, 0, n-1, i); } return a; }
#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...