| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 66951 |
2018-08-12T20:40:14 Z |
MKopchev |
Horses (IOI15_horses) |
C++14 |
|
672 ms |
49492 KB |
#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
const int nmax=5e5+42,mod=1e9+7,inf=1e9;
int n,x[nmax],y[nmax];
set<int> non_zero;
long long tree_x[4*nmax],tree_y[4*nmax];
void build_x(int node,int l,int r)
{
if(l==r)
{
tree_x[node]=x[l];
return;
}
int av=(l+r)/2;
build_x(node*2,l,av);
build_x(node*2+1,av+1,r);
tree_x[node]=(tree_x[node*2]*tree_x[node*2+1])%mod;
}
void update_x(int node,int l,int r,int pos,int val)
{
if(l==r)
{
tree_x[node]=val;
return;
}
int av=(l+r)/2;
if(pos<=av)update_x(node*2,l,av,pos,val);
else update_x(node*2+1,av+1,r,pos,val);
tree_x[node]=(tree_x[node*2]*tree_x[node*2+1])%mod;
}
int query_x(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree_x[node];
int av=(l+r)/2;
long long ans=1;
if(lq<=av)ans=ans*query_x(node*2,l,av,lq,min(av,rq))%mod;
if(av<rq)ans=ans*query_x(node*2+1,av+1,r,max(av+1,lq),rq)%mod;
return ans;
}
void build_y(int node,int l,int r)
{
if(l==r)
{
tree_y[node]=y[l];
return;
}
int av=(l+r)/2;
build_y(node*2,l,av);
build_y(node*2+1,av+1,r);
tree_y[node]=max(tree_y[node*2],tree_y[node*2+1]);
}
void update_y(int node,int l,int r,int pos,int val)
{
if(l==r)
{
tree_y[node]=val;
return;
}
int av=(l+r)/2;
if(pos<=av)update_y(node*2,l,av,pos,val);
else update_y(node*2+1,av+1,r,pos,val);
tree_y[node]=max(tree_y[node*2],tree_y[node*2+1]);
}
int query_y(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree_y[node];
int av=(l+r)/2;
int ans=1;
if(lq<=av)ans=max(ans,query_y(node*2,l,av,lq,min(av,rq)));
if(av<rq)ans=max(ans,query_y(node*2+1,av+1,r,max(av+1,lq),rq));
return ans;
}
bool bigger(long long a,long long b,long long c)
{
return a>=(c+b-1)/b;
}
int active[nmax],ind=0;
int query()
{
if(non_zero.size()==0)return /*query_y(1,0,n-1,0,n-1)*/-1;
long long prod=1,maxi=1;
int last=n,pos=-1;
ind=0;
for(auto k:non_zero)
{
pos=-k;
active[++ind]=pos;
prod=prod*x[pos];
if(prod>inf)break;
}
reverse(active+1,active+ind+1);
//cout<<"active: ";for(int i=1;i<=ind;i++)cout<<active[i]<<" ";cout<<endl;
prod=1;
for(int i=1;i<ind;i++)
{
prod=prod*x[active[i]];
//cout<<"q "<<query_y(1,0,n-1,active[i],active[i+1]-1)<<endl;
maxi=max(maxi,prod*query_y(1,0,n-1,active[i],active[i+1]-1));
}
if(ind==non_zero.size())
{
if(active[1]!=0)maxi=max(maxi,1LL*query_y(1,0,n-1,0,active[1]-1));
}
//cout<<maxi<<endl;
long long mult=1;
if(ind!=non_zero.size())mult=query_x(1,0,n-1,0,active[1]-1);
long long a=prod*x[active[ind]];
long long b=query_y(1,0,n-1,active[ind],n-1);
if(bigger(a,b,maxi))return a%mod*b%mod*mult%mod;
return maxi%mod*mult%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];
for(int i=0;i<N;i++)
if(x[i]!=1)
{
non_zero.insert(-i);
}
build_x(1,0,n-1);
build_y(1,0,n-1);
return query();
}
int updateX(int pos,int val)
{
if(x[pos]==1)non_zero.erase(-pos);
x[pos]=val;
if(x[pos]==1)non_zero.insert(-pos);
update_x(1,0,n-1,pos,val);
return query();
}
int updateY(int pos,int val)
{
y[pos]=val;
update_y(1,0,n-1,pos,val);
return query();
}
/*
int X[]={2,1,3};
int Y[]={3,4,1};
int main()
{
cout<<init(3,X,Y)<<endl;
cout<<updateY(1,2)<<endl;
}
*/
Compilation message
horses.cpp: In function 'int query_x(int, int, int, int, int)':
horses.cpp:34:39: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
if(l==lq&&r==rq)return tree_x[node];
~~~~~~~~~~~^
horses.cpp:39:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return ans;
^~~
horses.cpp: In function 'int query_y(int, int, int, int, int)':
horses.cpp:68:39: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
if(l==lq&&r==rq)return tree_y[node];
~~~~~~~~~~~^
horses.cpp: In function 'int query()':
horses.cpp:105:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ind==non_zero.size())
~~~^~~~~~~~~~~~~~~~~
horses.cpp:113:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ind!=non_zero.size())mult=query_x(1,0,n-1,0,active[1]-1);
~~~^~~~~~~~~~~~~~~~~
horses.cpp:118:48: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
if(bigger(a,b,maxi))return a%mod*b%mod*mult%mod;
~~~~~~~~~~~~~~~~^~~~
horses.cpp:119:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return maxi%mod*mult%mod;
~~~~~~~~~~~~~^~~~
horses.cpp:86:9: warning: unused variable 'last' [-Wunused-variable]
int last=n,pos=-1;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
588 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
588 KB |
Output is correct |
| 2 |
Correct |
2 ms |
592 KB |
Output is correct |
| 3 |
Correct |
2 ms |
616 KB |
Output is correct |
| 4 |
Correct |
2 ms |
616 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
744 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
672 ms |
49428 KB |
Output is correct |
| 2 |
Correct |
421 ms |
49492 KB |
Output is correct |
| 3 |
Correct |
412 ms |
49492 KB |
Output is correct |
| 4 |
Correct |
397 ms |
49492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
49492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
49492 KB |
Output is correct |
| 3 |
Correct |
3 ms |
49492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
49492 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
49492 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
49492 KB |
Output is correct |
| 2 |
Correct |
3 ms |
49492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
49492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
49492 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
49492 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
