| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 393048 |
2021-04-22T15:41:20 Z |
cpp219 |
Horses (IOI15_horses) |
C++14 |
|
1484 ms |
91860 KB |
#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e5 + 9;
const ll mod = 1e9 + 7;
ll X[N],Y[N],sz;
struct elem{
ll mu,nhan,md;
};
void Fix(elem &x){
x.nhan += x.md/mod; x.md %= mod;
x.mu += x.nhan/mod; x.nhan %= mod;
}
elem operator * (elem x,ll val){
elem now = {x.mu,x.nhan,x.md * val};
Fix(now); return now;
}
elem operator / (elem x,ll val){
ll cur = x.nhan*mod + x.md;
elem now = {x.mu,0,cur/val}; Fix(now); return now;
}
elem Maximum(elem x,elem y){
if (x.mu != y.mu){
if (x.mu > y.mu) return x;
return y;
}
if (x.nhan != y.nhan){
if (x.nhan > y.nhan) return x;
return y;
}
if (x.md > y.md) return x; return y;
}
elem st[4*N];
ll lazyC[4*N],lazyN[4*N];
void Pass(ll id){
ll v1 = lazyN[id],v2 = lazyC[id]; lazyN[id] = 1; lazyC[id] = 1;
st[id*2] = st[id*2] * v1; st[id*2] = st[id*2] / v2; lazyN[id*2] = v1; lazyC[id*2] = v2;
st[id*2 + 1] = st[id*2 + 1] * v1; st[id*2 + 1] = st[id*2 + 1] / v2;
lazyN[id*2 + 1] = v1; lazyC[id*2 + 1] = v2;
}
/// -val mean /val val mean *val
void upd(ll id,ll l,ll r,ll u,ll v,ll val){
if (v < l||r < u) return;
if (u <= l&&r <= v){
if (val > 0) st[id] = st[id] * abs(val),lazyN[id] = val;
else st[id] = st[id] / -val,lazyC[id] = -val;
return;
}
ll mid = (l + r)/2; Pass(id);
upd(id*2,l,mid,u,v,val); upd(id*2 + 1,mid + 1,r,u,v,val);
st[id] = Maximum(st[id*2],st[id*2 + 1]);
}
void out(elem x){
cout<<x.mu<<" "<<x.nhan<<" "<<x.md; exit(0);
}
int updateX(int pos,int val){
pos++;
upd(1,1,sz,pos,sz,-X[pos - 1]); upd(1,1,sz,pos,sz,val);
X[pos - 1] = val;
return st[1].md;
}
int updateY(int pos,int val){
pos++;
upd(1,1,sz,pos,pos,-Y[pos - 1]); upd(1,1,sz,pos,pos,val);
Y[pos - 1] = val;
return st[1].md;
}
int init(int n,int P[],int Q[]){
sz = n;
for (ll i = 1;i <= 4*n;i++){
lazyC[i] = lazyN[i] = 1;
st[i] = {0,0,1};
}
for (ll i = 0;i < n;i++){
X[i] = P[i]; Y[i] = Q[i];
upd(1,1,n,i + 1,n,P[i]); upd(1,1,n,i + 1,i + 1,Q[i]);
}
return st[1].md;
}
Compilation message
horses.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
1 | #pragma GCC optimization "Ofast"
|
horses.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
horses.cpp: In function 'elem Maximum(elem, elem)':
horses.cpp:43:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
43 | if (x.md > y.md) return x; return y;
| ^~
horses.cpp:43:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
43 | if (x.md > y.md) return x; return y;
| ^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:77:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
77 | return st[1].md;
| ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:84:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
84 | return st[1].md;
| ~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
97 | return st[1].md;
| ~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1484 ms |
91860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
