| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 621271 |
2022-08-03T16:13:47 Z |
A_D |
Horses (IOI15_horses) |
C++14 |
|
1500 ms |
44132 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+100;
long long x[N];
long long y[N];
long long seg[4*N];
const long long MOD=1e9+7;
int n;
long long me=1;
vector<int> vec;
set<int> st;
void build(int p,int s,int e)
{
if(s==e){
seg[p]=y[s];
return;
}
int mid=(s+e)/2;
build(p*2,s,mid);
build(p*2+1,mid+1,e);
seg[p]=max(seg[p*2],seg[p*2+1]);
}
void update(int p,int s,int e,int i,int v)
{
if(s==e){
seg[p]=v;
return;
}
int mid=(s+e)/2;
if(i<=mid){
update(p*2,s,mid,i,v);
}
else{
update(p*2+1,mid+1,e,i,v);
}
seg[p]=max(seg[p*2],seg[p*2+1]);
}
long long get(int p,int s,int e,int a,int b)
{
if(a<=s&&e<=b){
return seg[p];
}
if(s>b||e<a){
return 0;
}
int mid=(s+e)/2;
return max(get(p*2,s,mid,a,b),get(p*2+1,mid+1,e,a,b));
}
long long po(long long b,long long p)
{
if(p==0)return 1;
if(p==1)return b;
if(p%2){
return (b*po(b,p-1))%MOD;
}
long long r=po(b,p/2);
return (r*r)%MOD;
}
long long modinv(int v)
{
return po(v,MOD-2);
}
void fil()
{
int cnt=0;
for(auto x:st){
vec.push_back(-x);
cnt++;
if(cnt==31)break;
}
reverse(vec.begin(),vec.end());
}
int getans()
{
fil();
long long ret=seg[1];
long long sum=1,sum2=1,val=seg[1];
if(vec.size()==31)val=0;
for(auto i:vec){
sum*=x[i];
sum%=MOD;
sum2*=x[i];
if(sum2*get(1,0,n-1,i,n-1)>val){
val=y[i];
sum2=1;
ret=sum*get(1,0,n-1,i,n-1);
ret%=MOD;
}
}
return ret;
}
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){
st.insert(-i);
}
}
build(1,0,n-1);
fil();
int h;
if(vec.empty()){
h=n;
}
else h=vec[0];
for(int i=0;i<vec[0];i++){
me*=x[i];
me%=MOD;
}
return (getans()*me)%MOD;
}
int updateX(int pos, int val) {
fil();
if(vec.empty()){
if(val!=1){
st.insert(-pos);
}
x[pos]=val;
}
else{
if(vec.size()<31){
if(x[pos]==1){
if(val==1){
;
}
else{
x[pos]=val;
st.insert(-pos);
}
}
else{
if(val==1){
x[pos]=val;
st.erase(-pos);
}
else{
x[pos]=val;
}
}
}
else{
if(pos>=vec[0]){
if(x[pos]==1){
if(val==1){
;
}
else{
st.insert(-pos);
me*=x[vec[0]];
me%=MOD;
}
}
else{
if(val==1){
st.erase(-pos);
fil();
me*=modinv(x[vec[0]]);
me%=MOD;
}
else{
x[pos]=val;
}
}
}
else{
me*=modinv(x[pos]);
me%=MOD;
x[pos]=val;
me%=x[pos];
me%=MOD;
}
}
}
return (me*getans())%MOD;
}
int updateY(int pos, int val) {
update(1,0,n-1,pos,val);
return (getans()*me)%MOD;
}
Compilation message
horses.cpp: In function 'void fil()':
horses.cpp:70:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
70 | for(auto x:st){
| ^
horses.cpp:8:11: note: shadowed declaration is here
8 | long long x[N];
| ^
horses.cpp: In function 'int getans()':
horses.cpp:98:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
98 | return ret;
| ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:100:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
100 | int init(int N, int X[], int Y[]){
| ~~~~^
horses.cpp:7:11: note: shadowed declaration is here
7 | const int N=5e5+100;
| ^
horses.cpp:120:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
120 | return (getans()*me)%MOD;
| ~~~~~~~~~~~~~^~~~
horses.cpp:111:9: warning: variable 'h' set but not used [-Wunused-but-set-variable]
111 | int h;
| ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:169:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
169 | me*=modinv(x[vec[0]]);
| ~~~~~~~~^
horses.cpp:178:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
178 | me*=modinv(x[pos]);
| ~~~~~^
horses.cpp:190:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
190 | return (me*getans())%MOD;
| ~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:197:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
197 | return (getans()*me)%MOD;
| ~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1587 ms |
44132 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
