# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
833840 |
2023-08-22T08:56:51 Z |
pomuchle |
Horses (IOI15_horses) |
C++17 |
|
47 ms |
54004 KB |
#include "horses.h"
#include <cassert>
#include <vector>
#include <ios>
#define REP(i, n) for (int i=0; i<(n); ++i)
#define FOR(i, p, n) for (int i=(p); i<=(n); ++i)
#define V std::vector
typedef V <int> vi;
typedef long long ll;
typedef V <ll> vll;
#define CAP (ll(1e9+5))
#define MOD 1'000'000'007
struct stilnode{
ll m,c; // modulo i z capem
stilnode(){
m=c=0;
}
stilnode(int i){
m=c=i;
}
stilnode(ll nm, ll nc){
m=nm,c=nc;
}
stilnode operator^(const stilnode &i) const{
return {m*i.m%MOD, std::min(c*i.c, CAP)};
}
};
struct stiltype{
V <stilnode> t;
int comp;
stiltype(){}
stiltype(int n, int X[]){
for (comp=1; comp<n; comp<<=1);
t.resize(comp<<1);
--comp;
REP(i, n)
t[i+comp+1]=X[i];
for (int i=comp; i; --i)
t[i]=t[i<<1]^t[(i<<1)+1];
}
void wst(int i, int w){
t[i+=comp]=w;
for (i>>=1; i; i>>=1)
t[i]=t[i<<1]^t[(i<<1)+1];
}
stilnode zap(int p, int k){
stilnode r={1, 1};
for (p+=comp,k+=comp+1; p<k; p>>=1,k>>=1){
if (p&1)
r=r^t[p++];
if (k&1)
r=r^t[--k];
}
return r;
}
} stil;
struct stmintype{
vi t;
vi Y;
int comp;
int lacz(int i, int j){
if (!i||!j)
return i+j;
if (i>j)
std::swap(i, j);
ll lew=Y[i],praw=Y[j]*stil.zap(i+1, j).c;
return lew>=praw ? i : j;
}
stmintype(){}
stmintype(int n, int v[]){ // translacja v!!!
for (comp=1; comp<n; comp<<=1);
t.resize(comp<<1);
Y.resize(n+1);
--comp;
REP(i, n)
Y[i+1]=v[i];
FOR(i, 1, n)
t[i+comp]=i;
for (int i=comp; i; --i)
t[i]=lacz(t[i<<1], t[(i<<1)+1]);
}
void wst(int i, int w=0){
if (w) // w=0 -> noop
Y[i]=w;
for (i+=comp,i>>=1; i; i>>=1)
t[i]=lacz(t[i<<1], t[(i<<1)+1]);
}
} stmin;
int n;
int wynbru(){
ll l=1,w=0;
for (int i=1; i<=n; ++i){
l*=stil.t[i+stil.comp].m;
w=std::max(w, l*stmin.Y[i]);
}
return int(w%MOD);
}
int wyn(){
int wpos=stmin.t[1];
ll w=stil.zap(1, wpos).m*stmin.Y[wpos]%MOD;
assert(w==wynbru());
#ifdef LOCAL
printf("%lld\n", w);
#endif
return int(w);
}
int init(int N, int X[], int Y[]) {
n=N;
stil=stiltype(N, X);
stmin=stmintype(N, Y);
return wyn();
}
int updateX(int pos, int val) {
++pos;
stil.wst(pos, val);
stmin.wst(pos);
return wyn();
}
int updateY(int pos, int val) {
++pos;
stmin.wst(pos, val);
return wyn();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
292 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
47 ms |
54004 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
284 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
22 |
Halted |
0 ms |
0 KB |
- |