Submission #658379

#TimeUsernameProblemLanguageResultExecution timeMemory
658379jamezzzHorses (IOI15_horses)C++17
80 / 100
1519 ms217516 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second typedef long long ll; typedef pair<int,int> ii; #define mod 1000000007 struct node{ int s,e,m;ll v=1,lz=1; node *l,*r; node(int _s,int _e){ s=_s,e=_e,m=(s+e)>>1; if(s!=e)l=new node(s,m),r=new node(m+1,e); } void ppo(){ v=(v*lz)%mod; if(s!=e){ l->lz=(lz*l->lz)%mod; r->lz=(lz*r->lz)%mod; } lz=1; } void up(int x,int y,ll nv){ if(s==x&&e==y){lz=(lz*nv)%mod;return;} if(y<=m)l->up(x,y,nv); else if(x>m)r->up(x,y,nv); else l->up(x,m,nv),r->up(m+1,y,nv); l->ppo(),r->ppo(); v=max(l->v,r->v); } ll qry(int x,int y){ ppo(); if(s==x&&e==y)return v; if(y<=m)return l->qry(x,y); if(x>m)return r->qry(x,y); return max(l->qry(x,m),r->qry(m+1,y)); } void print(){ printf("%d %d %d %lld %lld\n",s,e,m,v,lz); if(s!=e)l->print(),r->print(); } }*rt; struct node2{ int s,e,m;ll v=1,lz=1; node2 *l,*r; node2(int _s,int _e){ s=_s,e=_e,m=(s+e)>>1; if(s!=e)l=new node2(s,m),r=new node2(m+1,e); } void ppo(){ v=(v*lz)%mod; if(s!=e){ l->lz=(lz*l->lz)%mod; r->lz=(lz*r->lz)%mod; } lz=1; } void up(int x,int y,ll nv){ if(s==x&&e==y){lz=(lz*nv)%mod;return;} if(y<=m)l->up(x,y,nv); else if(x>m)r->up(x,y,nv); else l->up(x,m,nv),r->up(m+1,y,nv); l->ppo(),r->ppo(); v=(l->v*r->v)%mod; } ll qry(int x,int y){ ppo(); if(s==x&&e==y)return v; if(y<=m)return l->qry(x,y); if(x>m)return r->qry(x,y); return (l->qry(x,m)*r->qry(m+1,y))%mod; } void print(){ printf("%d %d %d %lld %lld\n",s,e,m,v,lz); if(s!=e)l->print(),r->print(); } }*pfx; struct node3{ int s,e,m,v; node3 *l,*r; node3(int _s,int _e){ s=_s,e=_e,m=(s+e)>>1,v=0; if(s!=e)l=new node3(s,m),r=new node3(m+1,e); } void up(int x,ll nv){ if(s==x&&e==x){v=nv;return;} if(x<=m)l->up(x,nv); else r->up(x,nv); v=max(l->v,r->v); } ll qry(int x,int y){ if(s==x&&e==y)return v; if(y<=m)return l->qry(x,y); if(x>m)return r->qry(x,y); return max(l->qry(x,m),r->qry(m+1,y)); } void print(){ printf("%d %d %d %lld\n",s,e,m,v); if(s!=e)l->print(),r->print(); } }*yrt; ll fp(ll x,int a){ if(a==0)return 1; ll t=fp(x,a/2); ll r=(t*t)%mod; if(a%2)r=(r*x)%mod; return r; } #define maxn 500005 int n,x[maxn],y[maxn]; set<ii> s; int ans(){ auto it=s.end(); ll mx=1; int pv=n; while(it!=s.begin()){ --it; auto[i,x]=*it; //check if [i,n-1] can be >1e9 mx=max(mx,yrt->qry(i,pv-1)); mx*=x; if(mx>1e9){ if(i==0)return mx%mod; ll f=pfx->qry(0,i-1); return (f*(mx%mod))%mod; } pv=i; } return rt->qry(0,n-1); } int init(int N,int X[],int Y[]){ n=N; rt=new node(0,n-1); pfx=new node2(0,n-1); yrt=new node3(0,n-1); for(int i=0;i<n;++i){ x[i]=X[i],y[i]=Y[i]; rt->up(i,n-1,x[i]); pfx->up(i,i,x[i]); rt->up(i,i,y[i]); yrt->up(i,y[i]); if(x[i]!=1)s.insert({i,x[i]}); } return ans(); } int updateX(int pos,int val){ if(x[pos]!=1)s.erase({pos,x[pos]}); rt->up(pos,n-1,fp(x[pos],mod-2)); pfx->up(pos,pos,fp(x[pos],mod-2)); rt->up(pos,n-1,val); pfx->up(pos,pos,val); x[pos]=val; if(val!=1)s.insert({pos,val}); return ans(); } int updateY(int pos,int val){ rt->up(pos,pos,fp(y[pos],mod-2)); rt->up(pos,pos,val); yrt->up(pos,val); y[pos]=val; return ans(); }

Compilation message (stderr)

horses.cpp: In member function 'void node3::up(int, ll)':
horses.cpp:91:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   if(s==x&&e==x){v=nv;return;}
      |                    ^~
horses.cpp: In member function 'void node3::print()':
horses.cpp:103:23: warning: format '%lld' expects argument of type 'long long int', but argument 5 has type 'int' [-Wformat=]
  103 |   printf("%d %d %d %lld\n",s,e,m,v);
      |                    ~~~^          ~
      |                       |          |
      |                       |          int
      |                       long long int
      |                    %d
horses.cpp: In function 'int ans()':
horses.cpp:126:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  126 |   auto[i,x]=*it;
      |          ^
horses.cpp:117:7: note: shadowed declaration is here
  117 | int n,x[maxn],y[maxn];
      |       ^
horses.cpp:130:6: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  130 |   if(mx>1e9){
      |      ^~
horses.cpp:131:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  131 |    if(i==0)return mx%mod;
      |                     ^
horses.cpp:133:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  133 |    return (f*(mx%mod))%mod;
      |                       ^
horses.cpp:137:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  137 |  return rt->qry(0,n-1);
      |         ~~~~~~~^~~~~~~
#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...