제출 #482972

#제출 시각아이디문제언어결과실행 시간메모리
482972MilosMilutinovic사탕 분배 (IOI21_candies)C++17
0 / 100
466 ms109284 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(random_device{}()); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=201000; int n,q; VI qs2[N]; vector<PII> qs[N]; ll pref4[N],mn[N],mx[N]; struct node{ ll valfg,val,mn,mx; node() {mn=mx=val=valfg=0;} }nd[4*N]; void upd(int p) { nd[p].mn=min(nd[p*2].mn,nd[p*2+1].mn); nd[p].mx=max(nd[p*2].mx,nd[p*2+1].mx); } void push(int p) { nd[p].val+=nd[p].valfg; // nd[p].mn=min(nd[p].mn,nd[p].mn+nd[p].valfg); // nd[p].mx=max(nd[p].mx,nd[p].mx+nd[p].valfg); nd[p].mn+=nd[p].valfg; nd[p].mx+=nd[p].valfg; nd[p*2].valfg+=nd[p].valfg; nd[p*2+1].valfg+=nd[p].valfg; nd[p].valfg=0; } //void updval(int p,int l,int r,int tl,int tr,int x) { // if (l>r||l>tr||r<tl) return; // if (tl<=l&&r<=tr) { // nd[p].valfg+=x; // push(p); // return; // } // push(p); // int md=(l+r)>>1; // updval(p*2,l,md,tl,tr,x); // updval(p*2+1,md+1,r,tl,tr,x); // upd(p); //} ll getmn(int p,int l,int r,int tl,int tr) { push(p); if (l>tr||r<tl) return 1e18; if (tl<=l&&r<=tr) return nd[p].mn; int md=(l+r)>>1; ll L=getmn(p*2,l,md,tl,tr); ll R=getmn(p*2+1,md+1,r,tl,tr); upd(p); return min(L,R); } ll getmx(int p,int l,int r,int tl,int tr) { push(p); if (l>tr||r<tl) return -1e18; if (tl<=l&&r<=tr) return nd[p].mx; int md=(l+r)>>1; ll L=getmx(p*2,l,md,tl,tr); ll R=getmx(p*2+1,md+1,r,tl,tr); upd(p); return max(L,R); } ll getval(int p,int l,int r,int x) { push(p); if (l==r) return nd[p].val; int md=(l+r)>>1; if (x<=md) return nd[p].valfg+getval(p*2,l,md,x); else return nd[p].valfg+getval(p*2+1,md+1,r,x); } void modify(int p,int l,int r,int tl,int tr,int x) { push(p); if (l>tr||r<tl) return; if (tl<=l&&r<=tr) { nd[p].valfg+=x; push(p); return; } push(p); int md=(l+r)>>1; modify(p*2,l,md,tl,tr,x); modify(p*2+1,md+1,r,tl,tr,x); upd(p); } VI distribute_candies(VI c,VI l,VI r,VI v) { n=SZ(c),q=SZ(v); VI a(n); // if (n<=2000&&q<=2000&&false) { // rep(i,0,q) rep(j,l[i],r[i]+1) a[j]+=v[i],a[j]=max(a[j],0),a[j]=min(a[j],c[j]); // return a; // } // bool sb2=true; // rep(i,0,q) if (v[i]<0) sb2=false; // if (sb2&&false) { // rep(i,0,q) { // qs2[l[i]].pb(v[i]); // qs2[r[i]+1].pb(-v[i]); // } // ll tot=0; // rep(i,0,n) { // for (auto x:qs2[i]) tot+=x; // a[i]=min((ll)c[i],tot); // } // return a; // } bool sb4=true; rep(i,0,q) if (l[i]!=0||r[i]!=n-1) sb4=false; if (sb4&&false) { printf("gas\n"); pref4[0]=v[0]; rep(i,1,q) pref4[i]=pref4[i-1]+v[i]; mx[q-1]=mn[q-1]=pref4[q-1]; per(i,0,q-1) mx[i]=max(pref4[i],mx[i+1]),mn[i]=min(pref4[i],mn[i+1]); rep(i,0,n) { // for (auto x:qs[i]) { // int id=x.fi; // int val=x.se; // updval(1,0,q-1,id,q-1,val); // } if (mx[0]-mn[0]<=c[i]) a[i]=pref4[q-1]-mn[0]; else { int l=0,r=q-1,pos=0; while (l<=r) { int md=(l+r)>>1; if (mx[md]-mn[md]>c[i]) pos=md,l=md+1; else r=md-1; } if (pref4[pos]<pref4[q-1]) a[i]=c[i]-(mx[pos]-pref4[q-1]); else a[i]=pref4[q-1]-mn[pos]; } } return a; } rep(i,0,q) { qs[l[i]].pb(mp(i+1,v[i])); qs[r[i]+1].pb(mp(i+1,-v[i])); } rep(i,0,n) { for (auto x:qs[i]) modify(1,0,q,x.fi,q-1,x.se); if (getmx(1,0,q,0,q)-getmn(1,0,q,0,q)<=c[i]) a[i]=getval(1,0,q,q)-getmn(1,0,q,0,q); else { int l=1,r=q,pos=0; while (l<=r) { int md=(l+r)>>1; if (getmx(1,0,q,md,q)-getmn(1,0,q,md,q)>c[i]) pos=md,l=md+1; else r=md-1; } printf("%d %d %d %d\n",pos,getmx(1,0,q,pos,q),getmn(1,0,q,pos,q),getval(1,0,q,pos+1)); if (getval(1,0,q,pos)<getval(1,0,q,q)) a[i]=c[i]-(getmx(1,0,q,pos,q)-getval(1,0,q,q)); else a[i]=getval(1,0,q,q)-getmn(1,0,q,pos,q); // rep(j,0,q) printf("%d ",getval(1,0,q-1,j)); puts(""); } } return a; }

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'VI distribute_candies(VI, VI, VI, VI)':
candies.cpp:162:16: warning: format '%d' expects argument of type 'int', but argument 3 has type 'll' {aka 'long long int'} [-Wformat=]
  162 |    printf("%d %d %d %d\n",pos,getmx(1,0,q,pos,q),getmn(1,0,q,pos,q),getval(1,0,q,pos+1));
      |               ~^              ~~~~~~~~~~~~~~~~~~
      |                |                   |
      |                int                 ll {aka long long int}
      |               %lld
candies.cpp:162:19: warning: format '%d' expects argument of type 'int', but argument 4 has type 'll' {aka 'long long int'} [-Wformat=]
  162 |    printf("%d %d %d %d\n",pos,getmx(1,0,q,pos,q),getmn(1,0,q,pos,q),getval(1,0,q,pos+1));
      |                  ~^                              ~~~~~~~~~~~~~~~~~~
      |                   |                                   |
      |                   int                                 ll {aka long long int}
      |                  %lld
candies.cpp:162:22: warning: format '%d' expects argument of type 'int', but argument 5 has type 'll' {aka 'long long int'} [-Wformat=]
  162 |    printf("%d %d %d %d\n",pos,getmx(1,0,q,pos,q),getmn(1,0,q,pos,q),getval(1,0,q,pos+1));
      |                     ~^                                              ~~~~~~~~~~~~~~~~~~~
      |                      |                                                    |
      |                      int                                                  ll {aka long long int}
      |                     %lld
#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...