Submission #1090551

#TimeUsernameProblemLanguageResultExecution timeMemory
1090551owoovoHorses (IOI15_horses)C++17
37 / 100
450 ms48736 KiB
#include "horses.h" #include<bits/stdc++.h> #define ll long long #define ld double #define F first #define S second #define lc id*2+1 #define rc id*2+2 using namespace std; const ll p=1e9+7; ll pw(ll a,ll b){ ll ans=1; while(b){ if(b&1)ans*=a,ans%=p; b>>=1,a*=a,a%=p; } return ans; } ll x[500010],y[500010],n; struct BIT{ ll ori[500010]; void init(){ for(int i=0;i<=n;i++)ori[i]=1; return; } void modify(ll x,int pos){ while(pos<=n){ ori[pos]*=x; ori[pos]%=p; pos+=pos&(-pos); } return; } ll query(ll pos){ ll ans=1; while(pos){ ans*=ori[pos]; ans%=p; pos-=pos&(-pos); } return ans; } }bit; struct SEG_TREE{ pair<int,int> ori[2000010]; void build(int l,int r,int id){ if(l==r){ ori[id]={y[l],l}; return; } int m=(l+r)>>1; build(l,m,lc); build(m+1,r,rc); ori[id]=max(ori[lc],ori[rc]); return; } void modify(int l,int r,int pos,int id,int x){ if(l==pos&&r==pos){ ori[id]={x,l}; return; } int m=(l+r)>>1; if(pos<=m){ modify(l,m,pos,lc,x); }else{ modify(m+1,r,pos,rc,x); } ori[id]=max(ori[lc],ori[rc]); return; } pair<int,int> query(int l,int r,int ql,int qr,int id){ if(l==ql&&r==qr){ return ori[id]; } int m=(l+r)>>1; if(qr<=m){ return query(l,m,ql,qr,lc); }else if(m<ql){ return query(m+1,r,ql,qr,rc); }else{ return max(query(l,m,ql,m,lc),query(m+1,r,m+1,qr,rc)); } } }seg; set<int> big; ll q(){ if(big.size()==1){ return seg.query(1,n,1,n,0).F; } set<int>::iterator k=(--(--big.end())); ll pos=0; int now=0; ld nw=0,maxn=0; while(now<32&&k!=big.begin()){ now++; k--; } while(k!=(--big.end())){ nw+=log2(x[*k]); set<int>::iterator nx=k; nx++; //cout<<*k<<" "<<*(nx)<<"\n"; pair<int,int> pp=seg.query(1,n,*k,*(nx)-1,0); //cout<<pp.F<<" "<<pp.S<<"\n"; if(maxn<nw+log2(pp.F)){ maxn=nw+log2(pp.F); pos=pp.S; } k=nx; } ll a=bit.query(pos); //cout<<a<<"?\n"; a*=y[pos]; //cout<<a<<" 888\n"; a%=p; //cout<<pos<<"\n"; return a; } int init(int N, int X[], int Y[]) { n=N; big.insert(n+1); bit.init(); for(int i=0;i<n;i++){ x[i+1]=X[i]; bit.modify(x[i+1],i+1); if(x[i+1]>1)big.insert(i+1); y[i+1]=Y[i]; } seg.build(1,n,0); return q(); } int updateX(int pos, int val) { pos+=1; bit.modify((pw(x[pos],p-2)*val)%p,pos); x[pos]=val; if(val==1)big.erase(pos); else big.insert(pos); return q(); } int updateY(int pos, int val) { pos+=1; seg.modify(1,n,pos,0,val); y[pos]=val; return q(); }

Compilation message (stderr)

horses.cpp: In member function 'void BIT::modify(long long int, int)':
horses.cpp:26:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   26 |  void modify(ll x,int pos){
      |                 ^
horses.cpp:19:4: note: shadowed declaration is here
   19 | ll x[500010],y[500010],n;
      |    ^
horses.cpp: In member function 'void SEG_TREE::modify(int, int, int, int, int)':
horses.cpp:57:45: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   57 |  void modify(int l,int r,int pos,int id,int x){
      |                                         ~~~~^
horses.cpp:19:4: note: shadowed declaration is here
   19 | ll x[500010],y[500010],n;
      |    ^
horses.cpp: In function 'long long int q()':
horses.cpp:90:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |   return seg.query(1,n,1,n,0).F;
      |                      ^
horses.cpp:90:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |   return seg.query(1,n,1,n,0).F;
      |                          ^
horses.cpp:105:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  105 |   pair<int,int> pp=seg.query(1,n,*k,*(nx)-1,0);
      |                                ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:124:14: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
  124 |  big.insert(n+1);
      |             ~^~
horses.cpp:132:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |  seg.build(1,n,0);
      |              ^
horses.cpp:133:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |  return q();
      |         ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:142:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  142 |  return q();
      |         ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:147:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  147 |  seg.modify(1,n,pos,0,val);
      |               ^
horses.cpp:149:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  149 |  return q();
      |         ~^~
#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...