| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 761888 |
2023-06-20T10:59:43 Z |
Ahmed57 |
Horses (IOI15_horses) |
C++17 |
|
380 ms |
68172 KB |
#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
//Fast
long long fast(long long a,long long b){
if(b==0)return 1;
if(b==1)return a%mod;
long long ha = fast(a,b/2)%mod;
if(b%2==0)return (ha*ha)%mod;
else return (((ha*ha)%mod)*a)%mod;
}
long long seg[800001],lazy[800001];
long long seg2[800001],lazy2[800001];
void prop(int p,int l,int r){
seg[p]*=lazy[p];
seg[p]%=mod;
seg2[p]+=lazy2[p];
if(l!=r){
lazy[p*2]*=lazy[p];
lazy[p*2]%=mod;
lazy2[p*2]+=lazy2[p];
lazy[p*2+1]*=lazy[p];
lazy[p*2+1]%=mod;
lazy2[p*2+1]+=lazy2[p];
}
lazy[p] = 1;
lazy2[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,long long val,long long val2){
prop(p,l,r);
if(l>=lq&&r<=rq){
lazy[p]*=val;
lazy[p]%=mod;
lazy2[p]+=val2;
prop(p,l,r);
return ;
}
if(l>rq||r<lq)return ;
int md = (l+r)/2;
update(p*2,l,md,lq,rq,val,val2);
update(p*2+1,md+1,r,lq,rq,val,val2);
if(seg2[p*2]>seg2[p*2+1]){
seg2[p]= seg2[p*2];
seg[p] = seg[p*2];
}else{
seg2[p]= seg2[p*2+1];
seg[p] = seg[p*2+1];
}
}
pair<long long,long long> query(int p,int l,int r,int lq,int rq){
prop(p,l,r);
if(l>=lq&&r<=rq)return {seg[p],seg2[p]};
if(l>rq||r<lq)return {0,-1};
int md = (l+r)/2;
pair<long long,long long> p1 = query(p*2,l,md,lq,rq);
pair<long long,long long> p2 = query(p*2+1,md+1,r,lq,rq);
if(p1.second>p2.second)return p1;
else return p2;
}
int n;
vector<long long> x,y;
int init(int N,int X[],int Y[]){
n = N;
for(int i = 0;i<=8e5;i++){
seg[i] = 1, lazy[i] = 1;
seg2[i] = 0 , lazy2[i] = 0;
}
for(int i = 0;i<n;i++){
x.push_back(X[i]);
y.push_back(Y[i]);
update(1,1,n,i+1,n,X[i],log2(X[i]));
update(1,1,n,i+1,i+1,Y[i],log2(Y[i]));
}
return query(1,1,n,1,n).first;
}
int updateX(int pos,int val){
update(1,1,n,pos+1,n,fast(x[pos],mod-2),-log2(x[pos]));
x[pos] = val;
update(1,1,n,pos+1,n,x[pos],log2(x[pos]));
return query(1,1,n,1,n).first;
}int updateY(int pos,int val){
update(1,1,n,pos+1,pos+1,fast(y[pos],mod-2),-log2(y[pos]));
y[pos] = val;
update(1,1,n,pos+1,pos+1,y[pos],log2(y[pos]));
return query(1,1,n,1,n).first;
}/*
int main(){
init(3,{2,1,3},{3,4,1});
cout<<updateX(0,1)<<endl;
}*/
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:71:37: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
71 | update(1,1,n,i+1,n,X[i],log2(X[i]));
| ~~~~^~~~~~
horses.cpp:72:39: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
72 | update(1,1,n,i+1,i+1,Y[i],log2(Y[i]));
| ~~~~^~~~~~
horses.cpp:74:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
74 | return query(1,1,n,1,n).first;
| ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:77:46: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
77 | update(1,1,n,pos+1,n,fast(x[pos],mod-2),-log2(x[pos]));
| ^~~~~~~~~~~~~
horses.cpp:79:38: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
79 | update(1,1,n,pos+1,n,x[pos],log2(x[pos]));
| ~~~~^~~~~~~~
horses.cpp:80:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
80 | return query(1,1,n,1,n).first;
| ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:82:50: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
82 | update(1,1,n,pos+1,pos+1,fast(y[pos],mod-2),-log2(y[pos]));
| ^~~~~~~~~~~~~
horses.cpp:84:42: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'long long int' may change value [-Wfloat-conversion]
84 | update(1,1,n,pos+1,pos+1,y[pos],log2(y[pos]));
| ~~~~^~~~~~~~
horses.cpp:85:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
85 | return query(1,1,n,1,n).first;
| ~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
25300 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
25268 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
25268 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
25300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
380 ms |
68172 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
25300 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
25300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
25264 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
25344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
