| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 74006 | aleksam | 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>
#define MAX_N 500000
#define MOD 1000000007
#define debug 0
using namespace std;
int segtree[4*MAX_N], N;
long long X[MAX_N], Y[MAX_N];
long long partX[4*MAX_N];
struct classcomp {
bool operator() (const int& lhs, const int& rhs) const
{return lhs>rhs;}
};
set<int> S;//Skup indexa na kojima X[i]>1
void maketree(int l, int r, int v){
if(l+1>=r){
if(l==r-1){
segtree[v]=l;
partX[v]=X[l];
return;
}
/*segtree[v]=-1;
partX[v]=1;*/
assert(0);
return;
}
int mid=(l+r)/2;
maketree(l, mid, 2*v+1);
maketree(mid, r, 2*v+2);
partX[v]=partX[2*v+1]*partX[2*v+2];
partX[v]%=MOD;
if(segtree[2*v+1]==-1){
segtree[v]=segtree[2*v+2];
return;
}
if(segtree[2*v+2]==-1){
segtree[v]=segtree[2*v+1];
return;
}
segtree[v]=Y[segtree[2*v+1]]>Y[segtree[2*v+2]]?segtree[2*v+1]:segtree[2*v+2];
return;
}
int query(int ql, int qr, int l, int r, int v){
//if(debug)printf("rmq(%d, %d, %d, %d)\n", ql, qr, l, r);
if(ql>=r || qr<=l){
return -1;
}
if(ql<=l && r<=qr){
return segtree[v];
}
int q1, q2;
q1=query(ql, qr, l, (l+r)/2, 2*v+1);
q2=query(ql, qr, (l+r)/2, r, 2*v+2);
if(q1==-1)return q2;
if(q2==-1)return q1;
return Y[q1]>Y[q2]?q1:q2;
}
int partquery(int ql, int qr, int l, int r, int v){
if(ql>=r || qr<=l){
return -1;
}
if(ql<=l && r<=qr){
return partX[v];
}
long long q1, q2;
q1=partquery(ql, qr, l, (l+r)/2, 2*v+1);
q2=partquery(ql, qr, (l+r)/2, r, 2*v+2);
return (q1*q2)%MOD;
}
int rmq(int ql, int qr){//Vraca index!!!
//printf("rmq(%d, %d)\n", ql, qr);
return query(ql, qr, 0, N, 0);
}
int partXX(int pos){
long long ret=1;
for(int i=0; i<pos+1; ++i){
ret*=X[i];
if(ret>MOD)ret%=MOD;
}
return ret;
//return partquery(0, pos+1, 0, N, 0);
}
void updatetree(int l, int r, int v, int x){
if(l+1>=r){
return;
}
if(l<=x && x<r){
updatetree(l, (l+r)/2, 2*v+1, x);
updatetree((l+r)/2, r, 2*v+2, x);
if(segtree[2*v+1]==-1){
segtree[v]=segtree[2*v+2];
return;
}
if(segtree[2*v+2]==-1){
segtree[v]=segtree[2*v+1];
return;
}
segtree[v]=Y[segtree[2*v+1]]>Y[segtree[2*v+2]]?segtree[2*v+1]:segtree[2*v+2];
}
}
void updatepart(int l, int r, int v, int x){
if(l+1>=r){
return;
}
if(l<=x && x<r){
updatetree(l, (l+r)/2, 2*v+1, x);
updatetree((l+r)/2, r, 2*v+2, x);
partX[v]=(partX[2*v+1]*partX[2*v+2])%MOD;
}
}
vector<int> big;//Indexi svih X-eva koji su veci od 1
int num_big=0;
int solve(){
big.clear();//Moze brze
long long pi=1;
for(auto i:S){
pi*=X[i];
big.push_back(i);
if(pi>1000000000)break;
}
if(pi<1000000000)big.push_back(0);
pi=1;
int d=big.size();
if(debug){
for(int i=0; i<d; ++i)printf("%d ", big[i]);
printf("\n");
}
long long totmax=0, indmax=-1;
for(int i=0; i<d; ++i){
long long maxy;
if(i!=d-1){
maxy=rmq(big[i], big[i+1]);
}
else {
maxy=rmq(big[i], N);
//printf("ovde\n");
}
if(debug){printf("Iteracija i=%d, big[i]=%d, maxy=%d, pi=%d\n", i, big[i], maxy, pi);}
if(i!=0)pi*=X[big[i]];
if((long long)Y[maxy]*pi>totmax){
totmax=(long long)Y[maxy]*pi;
indmax=maxy;
}
}
//printf("totmax=%d, indmax=%d\n", totmax, indmax);
//printf("partXX(indmax)=%d\n", partXX(indmax));
long long res=(long long)Y[indmax]*partXX(indmax);
//printf("%d\n", res%MOD);
return res%MOD;
}
int init(int n, int x[], int y[]) {
N=n;
for(int i=0; i<N; ++i){
X[i]=x[i];
Y[i]=y[i];
if(X[i]>1){
S.insert(i);
num_big++;
}
}
maketree(0, N, 0);
if(debug){
for(int i=0; i<4*N; ++i){
printf("%*d ", 3, i);
}
printf("\n");
for(int i=0; i<4*N; ++i){
printf("%*d ", 3, segtree[i]);
}
printf("\n");
for(int i=0; i<4*N; ++i){
printf("%*d ", 3, partX[i]);
}
printf("\n");
}
return solve();
}