| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 669688 |
2022-12-07T05:32:06 Z |
alvingogo |
Horses (IOI15_horses) |
C++14 |
|
1500 ms |
47192 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
const int mod=1e9+7;
int mul(int x,int y){
return 1ll*x*y%mod;
}
struct ST{
vector<pair<int,int> > st;
void init(int n){
st.resize(4*n);
}
void pull(int v){
st[v].fs=mul(st[2*v+1].fs,st[2*v+2].fs);
st[v].sc=max(st[2*v+1].sc,st[2*v+2].sc);
}
void update(int v,int L,int R,int p,int t,int x){
if(L==R){
if(t==1){
st[v].fs=x;
}
else{
st[v].sc=x;
}
return;
}
int m=(L+R)/2;
if(p<=m){
update(2*v+1,L,m,p,t,x);
}
else{
update(2*v+2,m+1,R,p,t,x);
}
pull(v);
}
int q1(int v,int L,int R,int l,int r){
if(r<l){
return 1;
}
if(L==l && r==R){
return st[v].fs;
}
int m=(L+R)/2;
if(r<=m){
return q1(2*v+1,L,m,l,r);
}
else if(l>m){
return q1(2*v+2,m+1,R,l,r);
}
else{
return mul(q1(2*v+1,L,m,l,m),q1(2*v+2,m+1,R,m+1,r));
}
}
int q2(int v,int L,int R,int l,int r){
if(L==l && r==R){
return st[v].sc;
}
int m=(L+R)/2;
if(r<=m){
return q2(2*v+1,L,m,l,r);
}
else if(l>m){
return q2(2*v+2,m+1,R,l,r);
}
else{
return max(q2(2*v+1,L,m,l,m),q2(2*v+2,m+1,R,m+1,r));
}
}
}st;
set<pair<int,int> > s;
vector<int> x,y;
const int inf=2e9;
int n;
int cal(){
long long nw=1;
int lst=n;
for(auto h:s){
nw=max(nw,(long long)st.q2(0,0,n-1,-h.fs,lst-1));
nw*=h.sc;
if(nw>=inf){
return mul(nw,st.q1(0,0,n-1,0,-h.fs-1));
}
lst=h.fs;
}
return nw;
}
int init(int N,int X[],int Y[]){
st.init(N);
n=N;
for(int i=0;i<n;i++){
st.update(0,0,n-1,i,1,X[i]);
x.push_back(X[i]);
st.update(0,0,n-1,i,2,Y[i]);
y.push_back(Y[i]);
if(X[i]>=2 || i==0){
s.insert({-i,X[i]});
}
}
return cal();
}
int updateX(int pos,int val){
st.update(0,0,n-1,pos,1,val);
if(x[pos]>=2){
s.erase({-pos,x[pos]});
}
x[pos]=val;
if(x[pos]>=2){
s.insert({-pos,x[pos]});
}
return cal();
}
int updateY(int pos,int val){
st.update(0,0,n-1,pos,2,val);
y[pos]=val;
return cal();
}
Compilation message
horses.cpp: In function 'int mul(int, int)':
horses.cpp:11:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
11 | return 1ll*x*y%mod;
| ~~~~~~~^~~~
horses.cpp: In function 'int cal()':
horses.cpp:88:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
88 | return mul(nw,st.q1(0,0,n-1,0,-h.fs-1));
| ^~
horses.cpp:92:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
92 | return nw;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1581 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1581 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1576 ms |
47192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1555 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
1597 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
