| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 620784 |
2022-08-03T09:10:59 Z |
A_D |
Horses (IOI15_horses) |
C++14 |
|
231 ms |
92696 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+100;
const long long MOD=1e9+7;
long long x[N];
long long y[N];
set<int> st;
long long sum=1;
int n;
vector<int> vec;
long long seg[4*N];
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 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 val)
{
if(s==e){
seg[p]=val;
return;
}
int mid=(s+e)/2;
if(i<=mid){
update(p*2,s,mid,i,val);
}
else{
update(p*2+1,mid+1,e,i,val);
}
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 getansst()
{
long long ret=seg[1];
long long sum=1;
for(auto i:vec){
sum*=x[i];
long long u=sum*get(1,0,n-1,i,n-1);
if(u>ret){
sum%=MOD;
ret=sum*get(1,0,n-1,i,n-1);
}
}
ret%=MOD;
}
void filvec()
{
vec.clear();
int cnt=0;
for(auto x:st){
cnt++;
if(cnt==31)continue;
vec.push_back(-x);
}
reverse(vec.begin(),vec.end());
}
int init(int N, int X[], int Y[]){
st.clear();
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);
filvec();
if(vec.empty()){
sum=1;
return seg[1];
}
else{
int h=vec[0];
for(int i=0;i<h;i++){
sum*=x[i];
sum%=MOD;
}
long long u=getansst();
u*=sum;
u%=MOD;
return (int)u;
}
}
int updateX(int pos, int val) {
filvec();
int sz=vec.size();
if(x[pos]!=1){
st.erase(-pos);
}
if(val!=1){
st.insert(-pos);
}
if(st.size()<=31){
filvec();
x[pos]=val;
sum=1;
long long u=getansst();
return (int)u;
}
else{
int h=vec[0];
if(pos<h){
sum*=modinv(x[pos]);
sum%=MOD;
x[pos]=val;
sum*=x[pos];
sum%=MOD;
}
else{
if(val!=1){
st.erase(-pos);
}
if(x[pos]!=1){
st.insert(-pos);
}
if(x[pos]!=1){
if(val!=1){
x[pos]=val;
}
else{
int cnt=0;
int u;
for(auto x:st){
cnt++;
u=x;
if(cnt==32)break;
}
u*=-1;
st.erase(pos);
sum*=modinv(x[u]);
sum%=MOD;
x[pos]=val;
}
}
else{
if(val!=1){
x[pos]=val;
st.insert(-pos);
sum*=vec[h];
sum%=MOD;
}
else{
x[pos]=val;
}
}
}
}
long long u=getansst();
u*=sum;
u%=MOD;
return (int)u;
}
int updateY(int pos, int val) {
update(1,0,n-1,pos,val);
long long u=getansst();
u*=sum;
u%=MOD;
return (int)u;
}
Compilation message
horses.cpp: In function 'long long int getansst()':
horses.cpp:77:15: warning: declaration of 'sum' shadows a global declaration [-Wshadow]
77 | long long sum=1;
| ^~~
horses.cpp:12:11: note: shadowed declaration is here
12 | long long sum=1;
| ^~~
horses.cpp:87:1: warning: no return statement in function returning non-void [-Wreturn-type]
87 | }
| ^
horses.cpp: In function 'void filvec()':
horses.cpp:92:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
92 | for(auto x:st){
| ^
horses.cpp:9:11: note: shadowed declaration is here
9 | long long x[N];
| ^
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=1e6+100;
| ^
horses.cpp:117:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
117 | return seg[1];
| ~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:138:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
138 | int sz=vec.size();
| ~~~~~~~~^~
horses.cpp:155:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
155 | sum*=modinv(x[pos]);
| ~~~~~^
horses.cpp:181:30: warning: declaration of 'x' shadows a global declaration [-Wshadow]
181 | for(auto x:st){
| ^
horses.cpp:9:11: note: shadowed declaration is here
9 | long long x[N];
| ^
horses.cpp:188:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
188 | sum*=modinv(x[u]);
| ~~~^
horses.cpp:138:9: warning: unused variable 'sz' [-Wunused-variable]
138 | int sz=vec.size();
| ^~
horses.cpp:186:22: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
186 | u*=-1;
| ~^~~~
| # |
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 |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
231 ms |
92696 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 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
