| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 62409 |
2018-07-28T11:16:39 Z |
Tenuun |
Horses (IOI15_horses) |
C++17 |
|
503 ms |
42992 KB |
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
int n, tr[2000000], id[500001];
ll bit[500001];
ll now=1;
vector<int>x, y;
set<int>a;
void update(int ind, int val){
if(ind==0) return;
while(ind<=500000){
bit[ind]*=val;
bit[ind]%=mod;
ind+=ind&-ind;
}
}
ll get(int ind){
if(ind<0) return 1;
ll ans=1;
while(ind>0){
ans*=bit[ind];
ans%=mod;
ind-=ind&-ind;
}
return ans;
}
void pre(){
fill(bit, bit+500001, 1);
//a.insert(-1);
a.insert(0);
for(int i=0; i<n; i++){
if(x[i]>1){
a.insert(i);
update(i+1, x[i]);
}
}
}
void build(int ind, int l, int r){
if(l==r){
tr[ind]=y[l];
id[l]=ind;
return;
}
build(ind*2, l, (l+r)/2);
build(ind*2+1, (l+r)/2+1, r);
tr[ind]=max(tr[ind*2], tr[ind*2+1]);
}
void upd(int ind){
if(ind==0) return;
tr[ind]=max(tr[ind*2], tr[ind*2+1]);
upd(ind/2);
}
ll rmq(int ind, int l, int r, int L, int R){
if(l==L && r==R) return tr[ind];
int m=(l+r)/2;
if(R<=m) return rmq(ind*2, l, m, L, R);
else if(L>m) return rmq(ind*2+1, m+1, r, L, R);
else{
return max(rmq(ind*2, l, m, L, m), rmq(ind*2+1, m+1, r, m+1, R));
}
}
ll find(){
ll ans=1;
ll now=rmq(1, 0, n-1, *prev(a.end()), n-1);
set<int>::iterator it;
for(it=prev(a.end()); it!=a.begin() && now<mod; it--){
if(now*x[*it]>mod) {
//it++;
break;
}
now*=x[*it];
}
ans=now;
now/=rmq(1, 0, n-1, *prev(a.end()), n-1);
for(set<int>::iterator tmp=prev((prev(a.end()))); tmp!=prev(it) && tmp!=a.begin(); tmp--){
now/=x[*next(tmp)];
ans=max(ans, now*rmq(1, 0, n-1, *tmp, *next(tmp)-1));
}
ans%=mod;
if(it!=a.begin()) {
ans*=get(*it+1);
//ans*=get(max(*it, *next(it))+1);
}
ans%=mod;
//ll res=1;
//for(; it!=a.begin(); it--){
//cout << *it << " " ;
//ans*=x[*it];
//res*=x[*it];
//res%=mod;
//ans%=mod;
//}
return ans;
}
int init(int N, int X[], int Y[]) {
n=N;
for(int i=0; i<n; i++) {x.push_back(X[i]); y.push_back(Y[i]);}
pre();
build(1, 0, n-1);
return find();
}
ll pw(ll o, ll p){
if(p==0) return 1;
ll ans=pw(o, p/2);
ans*=ans;
ans%=mod;
if(p%2) ans*=o;
ans%=mod;
return ans;
}
int updateX(int pos, int val){
if(x[pos]==1 && val==1) return find();
if(x[pos]>1 && val>1){
update(pos+1, pw(x[pos], mod-2));
update(pos+1, val);
x[pos]=val;
return find();
}
if(x[pos]==1){
a.insert(pos);
update(pos+1, val);
x[pos]=val;
}
else{
a.erase(pos);
update(pos+1, pw(x[pos], mod-2));
x[pos]=1;
}
return find();
}
int updateY(int pos, int val){
tr[id[pos]]=val;
upd(id[pos]/2);
return find();
}
/*int main() {
int N; cin >> N;
int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; i++) {
cin >> X[i];
}
for (int i = 0; i < N; i++) {
cin >> Y[i];
}
cout << init(N,X,Y) << endl;
int M; cin >> M;
int type, pos, val;
for (int i = 0; i < M; i++) {
cin >> type >> pos >> val;
if (type == 1) {
cout << updateX(pos,val) << endl;
} else if (type == 2) {
cout << updateY(pos,val) << endl;
}
}
return 0;
}*/
Compilation message
horses.cpp: In function 'long long int find()':
horses.cpp:74:8: warning: declaration of 'now' shadows a global declaration [-Wshadow]
ll now=rmq(1, 0, n-1, *prev(a.end()), n-1);
^~~
horses.cpp:9:4: note: shadowed declaration is here
ll now=1;
^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:111:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:125:40: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
if(x[pos]==1 && val==1) return find();
~~~~^~
horses.cpp:127:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
update(pos+1, pw(x[pos], mod-2));
~~^~~~~~~~~~~~~~~
horses.cpp:130:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
horses.cpp:139:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
update(pos+1, pw(x[pos], mod-2));
~~^~~~~~~~~~~~~~~
horses.cpp:142:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:148:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
return find();
~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
503 ms |
42788 KB |
Output is correct |
| 2 |
Correct |
394 ms |
42788 KB |
Output is correct |
| 3 |
Correct |
362 ms |
42788 KB |
Output is correct |
| 4 |
Correct |
364 ms |
42992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
42992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
42992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
