# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
830354 | Supersonic | Horses (IOI15_horses) | C++14 | 305 ms | 44328 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];
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);
}
}
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;
}
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];
if(x[i]>1)g1.insert(i);
}
//if(subtask3)exit(1);
//cout<<prod(0,2)<<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 updateX(int pos, int val) {
if(val==1&&g1.count(pos))g1.erase(pos);
if(val>1)g1.insert(pos);
x[pos]=val;
modify(pos,val);
/*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;}
}*/
ll c=1;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(auto i:vv){
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 updateY(int pos, int val) {
y[pos]=val;
/*ll mp=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;}
}*/
ll c=1;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(auto i:vv){
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);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |