(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

제출 #602355

#제출 시각아이디문제언어결과실행 시간메모리
602355rrrr10000사탕 분배 (IOI21_candies)C++17
100 / 100
462 ms46924 KiB
#include "candies.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; typedef tuple<ll,ll,ll> PP; typedef vector<ll> vi; typedef vector<vi> vvi; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++) #define pb emplace_back template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;} template<class T> void out(T a){cout<<a<<endl;} struct segtree{ ll n; vector<PP> seg; segtree(ll n_):n(n_),seg(n_*2){} PP f(PP a,PP b){ chmax(get<1>(a),get<0>(a)+get<1>(b)); chmin(get<2>(a),get<0>(a)+get<2>(b)); get<0>(a)+=get<0>(b); return a; } void update(ll i,PP x){ i+=n;seg[i]=x; for(i>>=1;i>0;i>>=1)seg[i]=f(seg[i*2],seg[i*2+1]); } PP rng(ll l,ll r){ PP resl(0,0,0),resr(0,0,0); for(l+=n,r+=n;l<r;l>>=1,r>>=1){ if(l&1)resl=f(resl,seg[l++]); if(r&1)resr=f(seg[--r],resr); } return f(resl,resr); } void debug(){ rep(i,n)cout<<'('<<get<0>(seg[i+n])<<','<<get<1>(seg[i+n])<<','<<get<2>(seg[i+n])<<')'; cout<<endl; } }; vector<int> distribute_candies(vector<int> C, vector<int> L,vector<int> R, vector<int> V) { ll n=C.size(),q=L.size(); vi c(n),l(q),r(q),v(q); rep(i,n)c[i]=C[i]; rep(i,q)l[i]=L[q-i-1]; rep(i,q)r[i]=R[q-i-1]+1; rep(i,q)v[i]=-V[q-i-1]; vvi add(n+1),ers(n+1); rep(i,q){ add[l[i]].pb(i);ers[r[i]].pb(i); } segtree seg(q); vector<int> res(n); rep(i,n){ for(ll x:add[i])seg.update(x,PP(v[x],max(0ll,v[x]),min(0ll,v[x]))); for(ll x:ers[i])seg.update(x,PP(0,0,0)); // out(c[i]); // seg.debug(); ll ok=0,ng=q+1; while(ng-ok>1){ ll md=(ok+ng)/2; auto tmp=seg.rng(0,md); if(get<1>(tmp)-get<2>(tmp)>c[i])ng=md; else ok=md; } if(ok==q)res[i]=-get<2>(seg.rng(0,q)); else if(get<0>(seg.rng(0,ng))<0)res[i]=c[i]-get<1>(seg.rng(0,ng)); else res[i]=-get<2>(seg.rng(0,ng)); } return res; }
#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...