Submission #62300

#TimeUsernameProblemLanguageResultExecution timeMemory
62300TenuunHorses (IOI15_horses)C++17
17 / 100
585 ms46916 KiB
#include<bits/stdc++.h> #define mod 1000000007 #define ll long long using namespace std; int n, tr[2000000], id[500001]; ll bit[500001]; ll now=1; vector<int>x, y; set<int>a; void update(int ind, int val){ if(ind==0) bit[0]=(bit[0]*val)%mod, ind++; while(ind<=500000){ bit[ind]*=val; bit[ind]%=mod; ind+=ind&-ind; } } ll get(int ind){ ll ans=bit[0]; while(ind){ ans*=bit[ind]; ans%=mod; ind-=ind&-ind; } return ans; } void pre(){ memset(bit, 1, sizeof bit); int last=-1; a.insert(-1); a.insert(0); for(int i=0; i<n; i++){ if(x[i]>1){ a.insert(i); update(i, x[i]); } } } void build(int ind, int l, int r){ if(l==r){ tr[ind]=y[l]; id[l]=ind; return; } build(ind*2, l, (l+r)/2); build(ind*2+1, (l+r)/2+1, r); tr[ind]=max(tr[ind*2], tr[ind*2+1]); } void upd(int ind){ if(ind==0) return; tr[ind]=max(tr[ind*2], tr[ind*2+1]); upd(ind/2); } ll rmq(int ind, int l, int r, int L, int R){ if(l==L && r==R) return tr[ind]; int m=(l+r)/2; if(R<=m) return rmq(ind*2, l, m, L, R); else if(L>m) return rmq(ind*2+1, m+1, r, L, R); else{ return max(rmq(ind*2, l, m, L, m), rmq(ind*2+1, m+1, r, m+1, R)); } } ll find(){ ll ans=1; ll now=rmq(1, 0, n-1, *prev(a.end()), n-1); set<int>::iterator it; for(it=prev(a.end()); it!=a.begin() && now<mod; it--){ if(now*x[*it]>mod) break; now*=x[*it]; } ans=now; now/=rmq(1, 0, n-1, *prev(a.end()), n-1); for(set<int>::iterator tmp=prev((prev(a.end()))); tmp!=prev(it) && tmp!=a.begin(); tmp--){ now/=x[*next(tmp)]; ans=max(ans, now*rmq(1, 0, n-1, *tmp, *next(tmp)-1)); } ans%=mod; if(it!=a.begin()) ans*=get(*it); ans%=mod; /*for(; it!=a.begin(); it--){ ans*=x[*it]; ans%=mod; }*/ return ans; } int init(int N, int X[], int Y[]) { n=N; for(int i=0; i<n; i++) {x.push_back(X[i]); y.push_back(Y[i]);} pre(); build(1, 0, n-1); return find(); } ll pw(ll o, ll p){ if(p==0) return 1; ll ans=pw(o, p/2); ans*=ans; ans%=mod; if(p%2) ans*=o; ans%=mod; return ans; } int updateX(int pos, int val){ if(x[pos]==1 && val==1) return find(); if(x[pos]>1 && val>1){ update(pos, pw(x[pos], mod-2)); update(pos, val); x[pos]=val; ///now/x[pos]*val; return find(); } else if(x[pos]==1){ a.insert(pos); update(pos, val); x[pos]=val; } else{ a.erase(a.find(pos)); update(pos, pw(x[pos], mod-2)); x[pos]=1; } return find(); } int updateY(int pos, int val){ tr[id[pos]]=val; upd(id[pos]/2); return find(); }

Compilation message (stderr)

horses.cpp: In function 'void pre()':
horses.cpp:34:6: warning: unused variable 'last' [-Wunused-variable]
  int last=-1;
      ^~~~
horses.cpp: In function 'long long int find()':
horses.cpp:74:5: warning: declaration of 'now' shadows a global declaration [-Wshadow]
  ll now=rmq(1, 0, n-1, *prev(a.end()), n-1);
     ^~~
horses.cpp:9:4: note: shadowed declaration is here
 ll now=1;
    ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:101:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return find();
         ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:115:37: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  if(x[pos]==1 && val==1) return find();
                                 ~~~~^~
horses.cpp:117:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   update(pos, pw(x[pos], mod-2));
               ~~^~~~~~~~~~~~~~~
horses.cpp:121:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return find();
          ~~~~^~
horses.cpp:130:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   update(pos, pw(x[pos], mod-2));
               ~~^~~~~~~~~~~~~~~
horses.cpp:133:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return find();
         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:139:13: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return find();
         ~~~~^~
#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...