| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 73997 |
2018-08-29T15:12:22 Z |
aleksam |
Horses (IOI15_horses) |
C++14 |
|
1500 ms |
48120 KB |
#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;
}
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);
//big.push_back(i);
num_big++;
}
}
maketree(0, N, 0);
if(debug){
for(int i=0; i<3*N; ++i){
printf("%*d ", 3, i);
}
printf("\n");
for(int i=0; i<3*N; ++i){
printf("%*d ", 3, segtree[i]);
}
printf("\n");
for(int i=0; i<3*N; ++i){
printf("%*d ", 3, partX[i]);
}
printf("\n");
}
return solve();
}
int updateX(int pos, int val) {
if(X[pos]==1 && val>1){
S.insert(pos);
X[pos]=val;
updatepart(0, N, 0, pos);
}
else if(X[pos]>1 && val==1){
S.erase(pos);
X[pos]=1;
updatepart(0, N, 0, pos);
}
else if(X[pos]>1 && val>1){
X[pos]=val;
updatepart(0, N, 0, pos);
}
return solve();
}
int updateY(int pos, int val) {
Y[pos]=val;
updatetree(0, N, 0, pos);
return solve();
}
Compilation message
horses.cpp: In function 'int partquery(int, int, int, int, int)':
horses.cpp:69:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return partX[v];
~~~~~~~^
horses.cpp:74:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return (q1*q2)%MOD;
^
horses.cpp: In function 'int partXX(int)':
horses.cpp:88:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return ret;
^~~
horses.cpp: In function 'int solve()':
horses.cpp:134:16: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int d=big.size();
~~~~~~~~^~
horses.cpp:149:86: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
if(debug){printf("Iteracija i=%d, big[i]=%d, maxy=%d, pi=%d\n", i, big[i], maxy, pi);}
^
horses.cpp:149:86: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
horses.cpp:159:50: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
long long res=(long long)Y[indmax]*partXX(indmax);
^
horses.cpp:161:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return res%MOD;
^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:186:30: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
printf("%*d ", 3, partX[i]);
~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
488 KB |
Output is correct |
| 3 |
Correct |
4 ms |
488 KB |
Output is correct |
| 4 |
Correct |
3 ms |
656 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
656 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
656 KB |
Output is correct |
| 2 |
Correct |
3 ms |
656 KB |
Output is correct |
| 3 |
Correct |
3 ms |
656 KB |
Output is correct |
| 4 |
Correct |
3 ms |
656 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
656 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1570 ms |
48120 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
48120 KB |
Output is correct |
| 2 |
Correct |
2 ms |
48120 KB |
Output is correct |
| 3 |
Correct |
3 ms |
48120 KB |
Output is correct |
| 4 |
Correct |
2 ms |
48120 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
48120 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
48120 KB |
Output is correct |
| 2 |
Correct |
2 ms |
48120 KB |
Output is correct |
| 3 |
Correct |
2 ms |
48120 KB |
Output is correct |
| 4 |
Correct |
3 ms |
48120 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
48120 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
