Submission #432885

#TimeUsernameProblemLanguageResultExecution timeMemory
432885daniel920712Horses (IOI15_horses)C++14
100 / 100
1350 ms111724 KiB
#include "horses.h" #include <iostream> #include <stdio.h> #include <stdlib.h> #include <set> using namespace std; long long XX[500005]; long long YY[500005]; long long how[500005]={0}; long long MOD=1e9+7; long long N; set < long long > all; struct A { long long l,r; long long con; long long big; A* nxl,*nxr; void build(long long ll,long long rr) { l=ll; r=rr; if(ll+1==rr) { con=XX[ll]; big=YY[ll]; return; } nxl=(A*) malloc(sizeof(A)); nxr=(A*) malloc(sizeof(A)); nxl->build(ll,(ll+rr)/2); nxr->build((ll+rr)/2,rr); con=nxl->con*nxr->con%MOD; big=max(nxl->big,nxr->big); } void cha(long long where,long long tt) { if(l==where&&r==where+1) { con=tt; return; } if(where<(l+r)/2) nxl->cha(where,tt); else nxr->cha(where,tt); con=nxl->con*nxr->con%MOD; } long long Find(long long ll,long long rr) { if(ll==l&&rr==r) return con; if(rr<=(l+r)/2) return nxl->Find(ll,rr); if(ll>=(l+r)/2) return nxr->Find(ll,rr); return nxl->Find(ll,(l+r)/2)*nxr->Find((l+r)/2,rr)%MOD; } void cha2(long long where,long long tt) { if(l==where&&r==where+1) { big=tt; return; } if(where<(l+r)/2) nxl->cha2(where,tt); else nxr->cha2(where,tt); big=max(nxl->big,nxr->big); } long long Find2(long long ll,long long rr) { if(ll==l&&rr==r) return big; if(rr<=(l+r)/2) return nxl->Find2(ll,rr); if(ll>=(l+r)/2) return nxr->Find2(ll,rr); return max(nxl->Find2(ll,(l+r)/2),nxr->Find2((l+r)/2,rr)); } }; A* root; int init(int N, int X[], int Y[]) { all.insert(-1); long long ans=0,t=1,i,now=0,xx,tt,aa; ::N=N; for(i=0;i<N;i++) { XX[i]=(long long) X[i]; YY[i]=(long long) Y[i]; if(XX[i]>=2) all.insert(i); } root=(A*)malloc(sizeof(A)); root->build(0,N); now=YY[N-1]; t=YY[N-1]; now*=XX[N-1]; ans=t*root->Find(0,N)%MOD; t*=XX[N-1]; xx=N-1; while(now<=1000000000) { tt=*prev(all.lower_bound(xx)); if(tt==-1) { if(xx) { aa=root->Find2(0,xx); if(aa>now) { now=aa; t=aa; } ans=now; } break; } else { aa=root->Find2(tt,xx); if(aa>now) { now=aa; t=aa; } //printf("%lld %lld %lld %lld \n",t,now,tt,xx); ans=t*root->Find(0,tt+1)%MOD; if(now<1000000000) now*=XX[tt]; else break; t*=XX[tt]; t%=MOD; xx=tt; } } return (int) ans; } int updateX(int pos, int val) { long long ans=0,t=1,i,now=0,xx,tt,aa; if(XX[pos]>=2) all.erase(pos); XX[pos]=(long long) val; if(XX[pos]>=2) all.insert(pos); root->cha(pos,val); now=YY[N-1]; t=YY[N-1]; now*=XX[N-1]; ans=t*root->Find(0,N)%MOD; t*=XX[N-1]; xx=N-1; while(now<=1000000000) { tt=*prev(all.lower_bound(xx)); if(tt==-1) { if(xx) { aa=root->Find2(0,xx); if(aa>now) { now=aa; t=aa; } ans=now; } break; } else { aa=root->Find2(tt,xx); if(aa>now) { now=aa; t=aa; } //printf("%lld %lld %lld %lld \n",t,now,tt,xx); ans=t*root->Find(0,tt+1)%MOD; if(now<1000000000) now*=XX[tt]; else break; t*=XX[tt]; t%=MOD; xx=tt; } } return (int) ans; } int updateY(int pos, int val) { long long ans=0,t=1,i,now=0,xx,tt,aa; YY[pos]=(long long) val; root->cha2(pos,val); now=YY[N-1]; t=YY[N-1]; now*=XX[N-1]; ans=t*root->Find(0,N)%MOD; t*=XX[N-1]; xx=N-1; while(now<=1000000000) { tt=*prev(all.lower_bound(xx)); if(tt==-1) { if(xx) { aa=root->Find2(0,xx); if(aa>now) { now=aa; t=aa; } ans=now; } break; } else { aa=root->Find2(tt,xx); if(aa>now) { now=aa; t=aa; } //printf("%lld %lld %lld %lld \n",t,now,tt,xx); ans=t*root->Find(0,tt+1)%MOD; if(now<1000000000) now*=XX[tt]; else break; t*=XX[tt]; t%=MOD; xx=tt; } } return (int) ans; }

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:74:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   74 | int init(int N, int X[], int Y[])
      |          ~~~~^
horses.cpp:11:11: note: shadowed declaration is here
   11 | long long N;
      |           ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:135:25: warning: unused variable 'i' [-Wunused-variable]
  135 |     long long ans=0,t=1,i,now=0,xx,tt,aa;
      |                         ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:188:25: warning: unused variable 'i' [-Wunused-variable]
  188 |     long long ans=0,t=1,i,now=0,xx,tt,aa;
      |                         ^
#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...