Submission #727016

#TimeUsernameProblemLanguageResultExecution timeMemory
727016Yell0Horses (IOI15_horses)C++17
100 / 100
1092 ms84260 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int MOD=1e9+7; ll modinv(ll a) { ll res=1; for(ll i=0;(1LL<<i)<=MOD-2;++i) { if((MOD-2)&(1LL<<i)) res=res*a%MOD; a=a*a%MOD; } return res; } int N; vector<ll> bit,X,Y; set<pii> iv; void upd(int i,int a) { for(;i<=N;i+=-i&i) bit[i]=bit[i]*a%MOD; } ll qry(int i) { ll res=1; for(;i>0;i-=-i&i) res=res*bit[i]%MOD; return res; } struct node{int l,r;ll mx=1;}; vector<node> seg; void bldmx(int l,int r,int i) { seg[i].l=l; seg[i].r=r; if(l==r) return; int mid=(l+r)/2; bldmx(l,mid,i*2); bldmx(mid+1,r,i*2+1); seg[i].mx=max(seg[i*2].mx,seg[i*2+1].mx); } void updmx(int p,ll v,int i) { if(seg[i].l==p&&p==seg[i].r) { seg[i].mx=v; return; } int mid=(seg[i].l+seg[i].r)/2; if(p<=mid) updmx(p,v,i*2); else updmx(p,v,i*2+1); seg[i].mx=max(seg[i*2].mx,seg[i*2+1].mx); } ll qrymx(int l,int r,int i) { if(seg[i].l==l&&seg[i].r==r) return seg[i].mx; int mid=(seg[i].l+seg[i].r)/2; if(r<=mid) return qrymx(l,r,i*2); else if(l>mid) return qrymx(l,r,i*2+1); else return max(qrymx(l,mid,i*2),qrymx(mid+1,r,i*2+1)); } ll fndmx() { ll pfx=1,sfx=1,mpfx=1; auto sti=--iv.end(); for(auto i=sti;i!=--iv.begin();--i) { sfx*=X[i->first]; sti=i; if(sfx>=(ll)1e9) break; } auto mxi=sti; for(auto i=sti;i!=iv.end();++i) { pfx*=X[i->first]; if(pfx/mpfx>qrymx(mxi->first,mxi->second,1)/qrymx(i->first,i->second,1)) { mxi=i; mpfx=pfx; } } return qry(mxi->first)*qrymx(mxi->first,mxi->second,1)%MOD; } int init(int n,int x[],int y[]) { N=n; bit.resize(N+2,1); X.resize(N+2,1); Y.resize(N+2,1); seg.resize(N*4); bldmx(1,N,1); for(int i=1;i<=N;++i) { upd(i,x[i-1]); X[i]=x[i-1]; updmx(i,y[i-1],1); Y[i]=y[i-1]; } int st=1,ed=1; for(int i=1;i<=N;++i) { ed=i; if(X[i]==1) { if(X[i-1]>1) st=i; if(X[i+1]>1||i==N) iv.insert({st,ed}); continue; } st=i; iv.insert({st,ed}); } return fndmx(); } int updateX(int i,int a) { ++i; if(X[i]==1&&a!=1) { pii old=*(--iv.upper_bound({i,INT_MAX})); if(old.first!=old.second) { iv.erase(old); if(i==old.first) iv.insert({old.first+1,old.second}); else if(i==old.second) iv.insert({old.first,old.second-1}); else { iv.insert({old.first,i-1}); iv.insert({i+1,old.second}); } iv.insert({i,i}); } } if(a==1&&X[i]!=1) { pii curr={i,i}; int st=0,ed=0; if(X[i-1]==1&&i!=1) { st=(--iv.lower_bound(curr))->first; iv.erase(--iv.lower_bound(curr)); } if(X[i+1]==1&&i!=N) { ed=(iv.upper_bound(curr))->second; iv.erase(iv.upper_bound(curr)); } iv.erase(curr); iv.insert({(st?st:i),(ed?ed:i)}); } upd(i,modinv(X[i])*a%MOD); X[i]=a; return fndmx(); } int updateY(int i,int a) { ++i; Y[i]=a; updmx(i,a,1); return fndmx(); }

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:99:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   99 |   return fndmx();
      |          ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:130:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  130 |   upd(i,modinv(X[i])*a%MOD);
      |         ~~~~~~~~~~~~~~^~~~
horses.cpp:132:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |   return fndmx();
      |          ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:138:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  138 |   return fndmx();
      |          ~~~~~^~
#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...