| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 830578 | Supersonic | Horses (IOI15_horses) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll h[500001];
ll x[500001];
ll y[500001];
bool subtask3=1;
int n;
set<int, greater<int>> g1;
ll tree[1048577];
pair<ll,int> ytree[1048577];
void modify(int k, int x) {
k += n;
tree[k] = x;
for (k /= 2; k >= 1; k /= 2) {
tree[k] = tree[2*k]*tree[2*k+1];
tree[k]%=((ll)1e9+7);
}
}
pair<ll,int> pmax(pair<ll,int> a,pair<ll,int> b){
if(a>b) return a;
return b;
}
ll prod(ll a, ll b) {
a += n; b += n;
ll s = 1;
while (a <= b) {
if (a%2 == 1) {s *= tree[a++];s%=((ll)1e9+7);}
if (b%2 == 0) {s *= tree[b--];s%=((ll)1e9+7);}
a /= 2; b /= 2;
}
return s;
}
void ymodify(int k, int x) {
if(k>2*n)exit(1);
k += n;
ytree[k] = {x,k-n};
for (k /= 2; k >= 1; k /= 2) {
ytree[k] = pmax(ytree[2*k],ytree[2*k+1]);
ytree[k].first%=((ll)1e9+7);
}
}
pair<ll,int> rmax(ll a,ll b){
if(b>2*n)exit(1);
a += n; b += n;
pair<ll,int> s = {0,0};
while (a <= b) {
if (a%2 == 1) {s = pmax(s,ytree[a++]);}
if (b%2 == 0) {s = pmax(s,ytree[b--]);}
a /= 2; b /= 2;
}
return s;
}
int init(int N, int X[], int Y[]) {
n=N;
if(n<=1000)subtask3=0;
for(int i=0;i<n;i++){
x[i]=X[i];
if(x[i]<2)subtask3=0;
modify(i,x[i]);
y[i]=Y[i];
ymodify(i,y[i]);
if(x[i]>1)g1.insert(i);
}
//if(subtask3)exit(1);
//cout<<rmax(2,2)<<endl;;
//for(int i=0;i<2*n;i++){cerr<<ytree[i].first<<' '<<ytree[i].second<<endl;}
if(!subtask3){
ll mp=0;ll c=1;
for(int i=1;i<n;i++){
c*=x[i];
if(c>y[mp]||y[i]>y[mp]||c*y[i]>y[mp]){mp=i;c=1;}
}
return (prod(0,mp)*y[mp])%((ll)1e9+7);
}
else{
ll mp=n-33;ll c=1;
for(int i=n-32;i<n;i++){
c*=x[i];
if(c>y[mp]||y[i]>y[mp]||c*y[i]>y[mp]){mp=i;c=1;}
}
return (prod(0,mp)*y[mp])%((ll)1e9+7);
}
}
int sc=500;
int updateX(int pos, int val) {
//cerr<<pos<<endl;
if(val==1&&g1.count(pos))g1.erase(pos);
if(val>1)g1.insert(pos);
x[pos]=val;
sc--;
//if(g1.empty())exit(1);
if(sc==0){for(int i=0;i<n;i++)if(rmax(i,i).second!=i)exit(1);sc=3000;}
modify(pos,val);
if(g1.empty()){
int mp=rmax(0,n-1).second;
return (prod(0,mp)*y[mp])%((ll)1e9+7);
}
ll c=x[0];ll mp=0;
vector<int> vv;int cn=34;
for(auto i:g1){vv.push_back(i);cn--;if(cn==0)break;}vv.push_back(0)
reverse(vv.begin(),vv.end());
for(int vvi=0;vvi<vv.size();vvi++){
int vi=vv[vvi];
int vni=n-1;if(vvi!=vv.size()-1)vni=vv[vvi+1]-1;
int i=rmax(vi,vni).second;
if(i>=n)exit(1);
c*=x[vi];
if(c>y[mp]||y[i]>y[mp]||c*y[i]>y[mp]){mp=i;c=1;}
}
return (prod(0,mp)*y[mp])%((ll)1e9+7);
}
int updateY(int pos, int val) {
y[pos]=val;
ymodify(pos,val);
if(g1.empty()){
int mp=rmax(0,n-1).second;
//cerr<<mp<<endl;
return (prod(0,mp)*y[mp])%((ll)1e9+7);
}
ll c=x[0];ll mp=0;
vector<int> vv;int cn=34;
for(auto i:g1){vv.push_back(i);cn--;if(cn==0)break;}
reverse(vv.begin(),vv.end());
for(int vvi=0;vvi<vv.size();vvi++){
int vi=vv[vvi];
int vni=n-1;if(vvi!=vv.size()-1)vni=vv[vvi+1]-1;
int i=rmax(vi,vni).second;
if(i>=n)exit(1);
c*=x[vi];
if(c>y[mp]||y[i]>y[mp]||c*y[i]>y[mp]){mp=i;c=1;}
}
return (prod(0,mp)*y[mp])%((ll)1e9+7);
}