| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 658237 |
2022-11-12T13:44:14 Z |
jamezzz |
Horses (IOI15_horses) |
C++17 |
|
1038 ms |
161804 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
#define mod 1000000007
struct node{
int s,e,m;ll v=1,lz=1;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void ppo(){
v=(v*lz)%mod;
if(s!=e){
l->lz=(lz*l->lz)%mod;
r->lz=(lz*r->lz)%mod;
}
lz=1;
}
void up(int x,int y,ll nv){
if(s==x&&e==y){lz=(lz*nv)%mod;return;}
if(y<=m)l->up(x,y,nv);
else if(x>m)r->up(x,y,nv);
else l->up(x,m,nv),r->up(m+1,y,nv);
l->ppo(),r->ppo();
v=max(l->v,r->v);
}
ll qry(int x,int y){
ppo();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return max(l->qry(x,m),r->qry(m+1,y));
}
void print(){
printf("%d %d %d %lld %lld\n",s,e,m,v,lz);
if(s!=e)l->print(),r->print();
}
}*rt;
struct node2{
int s,e,m;ll v=1,lz=1;
node2 *l,*r;
node2(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1;
if(s!=e)l=new node2(s,m),r=new node2(m+1,e);
}
void ppo(){
v=(v*lz)%mod;
if(s!=e){
l->lz=(lz*l->lz)%mod;
r->lz=(lz*r->lz)%mod;
}
lz=1;
}
void up(int x,int y,ll nv){
if(s==x&&e==y){lz=(lz*nv)%mod;return;}
if(y<=m)l->up(x,y,nv);
else if(x>m)r->up(x,y,nv);
else l->up(x,m,nv),r->up(m+1,y,nv);
l->ppo(),r->ppo();
v=(l->v*r->v)%mod;
}
ll qry(int x,int y){
ppo();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return (l->qry(x,m)*r->qry(m+1,y))%mod;
}
void print(){
printf("%d %d %d %lld %lld\n",s,e,m,v,lz);
if(s!=e)l->print(),r->print();
}
}*pfx;
ll fp(ll x,int a){
if(a==0)return 1;
ll t=fp(x,a/2);
ll r=(t*t)%mod;
if(a%2)r=(r*x)%mod;
return r;
}
#define maxn 500005
int n,x[maxn],y[maxn];
set<ii> s;
int ans(){
ii mx={n-1,x[n-1]};
auto it=s.end();
ll sfx=1;
int far=0;
while(it!=s.begin()){
--it;
sfx*=(*it).se;
if(sfx>1e9){
far=(*it).fi;
break;
}
}
//ans will never come from [0,far-1]
ll f=pfx->qry(0,far);
//case 1: max comes from [far+1,n-1]
rt->up(far+1,n-1,fp(f,mod-2));
ll ans=rt->qry(far+1,n-1);
rt->up(far+1,n-1,f);
//case 2: max comes from [far]
if(y[far]>ans)ans=y[far];
ans=(ans*f)%mod;
return ans;
}
int init(int N,int X[],int Y[]){
n=N;
rt=new node(0,n-1);
pfx=new node2(0,n-1);
for(int i=0;i<n;++i){
x[i]=X[i],y[i]=Y[i];
rt->up(i,n-1,x[i]);
pfx->up(i,n-1,x[i]);
rt->up(i,i,y[i]);
if(x[i]!=1)s.insert({i,x[i]});
}
return ans();
}
int updateX(int pos,int val){
if(x[pos]!=1)s.erase({pos,x[pos]});
rt->up(pos,n-1,fp(x[pos],mod-2));
pfx->up(pos,n-1,fp(x[pos],mod-2));
rt->up(pos,n-1,val);
pfx->up(pos,n-1,val);
x[pos]=val;
if(val!=1)s.insert({pos,val});
return ans();
}
int updateY(int pos,int val){
rt->up(pos,pos,fp(y[pos],mod-2));
rt->up(pos,pos,val);
y[pos]=val;
return ans();
}
Compilation message
horses.cpp: In function 'int ans()':
horses.cpp:103:6: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
103 | if(sfx>1e9){
| ^~~
horses.cpp:117:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
117 | return ans;
| ^~~
horses.cpp:96:5: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
96 | ii mx={n-1,x[n-1]};
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1038 ms |
161804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
