Submission #343344

#TimeUsernameProblemLanguageResultExecution timeMemory
343344bigDuckHorses (IOI15_horses)C++14
17 / 100
861 ms36892 KiB
#include "horses.h" #include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount ll mod=((ll)1e9)+7; int N; ll exp(ll x, ll e){ if(e==1){ return x%mod; } if(e==0){ return 1; } return (exp(x, e%2)*exp( (x*x)%mod, e/2))%mod; } ll inv(ll x){ return exp(x, mod-2); } ll prod=1ll; multiset<pii> suf; int x[500010], y[500010]; int seg[2000010]; void build_seg(int v, int tl, int tr){ if(tl==tr){ seg[v]=y[tl]; return; } int mid=(tl+tr)>>1ll; build_seg(2*v, tl, mid); build_seg(2*v+1, mid+1, tr); seg[v]=max(seg[2*v], seg[2*v+1]); return; } void update_seg(int v, int tl, int tr, int pos, int x){ if(tl==tr){ seg[v]=x; y[tl]=x; return; } int mid=(tl+tr)>>1ll; if(pos<=mid){ update_seg(2*v, tl, mid, pos, x); } else{ update_seg(2*v+1, mid+1, tr, pos, x); } seg[v]=max(seg[2*v], seg[2*v+1]); return; } int query(int v, int tl, int tr, int l, int r){ if(l>r){ return 0; } if( (tl==l) && (tr==r) ){ return seg[v]; } int mid=(tl+tr)>>1ll; int q1=query(2*v, tl, mid, l, min(r, mid)), q2=query(2*v+1, mid+1, tr, max(l, mid+1), r); return max(q1, q2); } int get_resp(int N){ ll prod2=1ll; ll res=y[N]; auto it=suf.end(); ll lt=N; if(it==suf.begin()){ res=query(1, 1, N, 1, lt); return (res*prod)%mod; } it--; for(;;it--){ ll pos=it->ft, X=it->sc; ll Y=query(1, 1, N, pos, lt); if( ((res*prod2)%mod)<Y ){ //cout<<res<<" "<<((res*prod2)%mod)<<" "<<Y<<" "<<prod<<"\n"; res=(Y*inv(prod2))%mod; } lt=pos-1; prod2*=X; if(prod2>((ll)1e9)){ break; } if(it==suf.begin()){ break; } } if( (prod2<((ll)1e9)) && (lt>0) ){ ll Y=query(1, 1, N, 1, lt); if( ((res*prod2)%mod)<Y ){ res=(Y*inv(prod2))%mod; } } res=(res*prod)%mod; return res; } int init(int n, int X[], int Y[]) { N=n; for(int i=1; i<=N; i++){ x[i]=X[i-1]; y[i]=Y[i-1]; } build_seg(1, 1, N); for(int i=1; i<=N; i++){ prod=(prod*x[i])%mod; } for(int i=1; i<=N; i++){ if(x[i]>1){ suf.insert({i, x[i]}); } } return get_resp(N); } int updateX(int pos, int val) { auto it=suf.lower_bound({pos+1, 0}); if( (it!=suf.end()) ){ if( (it->ft)==(pos+1) ){ prod=(prod*inv(it->sc))%mod; suf.erase(it); } } suf.insert({(pos+1), val}); prod=(prod*val)%mod; return get_resp(N); } int updateY(int pos, int val) { update_seg(1, 1, N, pos+1, val); return get_resp(N); }

Compilation message (stderr)

horses.cpp: In function 'void update_seg(int, int, int, int, int)':
horses.cpp:52:54: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   52 | void update_seg(int v, int tl, int tr, int pos, int x){
      |                                                      ^
horses.cpp:36:5: note: shadowed declaration is here
   36 | int x[500010], y[500010];
      |     ^
horses.cpp: In function 'int get_resp(int)':
horses.cpp:86:19: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   86 | int get_resp(int N){
      |                   ^
horses.cpp:15:5: note: shadowed declaration is here
   15 | int N;
      |     ^
horses.cpp:93:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |         res=query(1, 1, N, 1, lt);
      |                               ^~
horses.cpp:94:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   94 |         return (res*prod)%mod;
      |                ~~~~~~~~~~^~~~
horses.cpp:99:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |         ll Y=query(1, 1, N, pos, lt);
      |                             ^~~
horses.cpp:99:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |         ll Y=query(1, 1, N, pos, lt);
      |                                  ^~
horses.cpp:115:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |         ll Y=query(1, 1, N, 1, lt);
      |                                ^~
horses.cpp:122:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |     return res;
      |            ^~~
#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...