#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mid ((l+r) >> 1)
const ll INF = 1e9+1;
const int mod = 1e9+7;
int n, x[500500], y[500500];
ll t1[2002002], t3[2002002];
array<int, 2> t2[2002002];
set<int> s;
ll build1(int node = 1, int l = 0, int r = n-1){
if(l == r) return t1[node] = x[l];
return t1[node] = min(INF, build1(node*2, l, mid) * build1(node*2+1, mid+1, r));
}
array<int, 2> build2(int node = 1, int l = 0, int r = n-1){
if(l == r) return t2[node] = {y[l], l};
return t2[node] = max(build2(node*2, l, mid), build2(node*2+1, mid+1, r));
}
ll build3(int node = 1, int l = 0, int r = n-1){
if(l == r) return t3[node] = x[l];
return t3[node] = build3(node*2, l, mid) * build3(node*2+1, mid+1, r) % mod;
}
void update1(int pos, int val, int node = 1, int l = 0, int r = n-1){
if(pos < l || r < pos) return;
if(l == r){
t1[node] = val;
return;
}
update1(pos, val, node*2, l, mid), update1(pos, val, node*2+1, mid+1, r);
t1[node] = min(INF, t1[node*2] * t1[node*2+1]);
}
void update2(int pos, int val, int node = 1, int l = 0, int r = n-1){
if(pos < l || r < pos) return;
if(l == r){
t2[node][0] = val;
return;
}
update2(pos, val, node*2, l, mid), update2(pos, val, node*2+1, mid+1, r);
t2[node] = max(t2[node*2], t2[node*2+1]);
}
void update3(int pos, int val, int node = 1, int l = 0, int r = n-1){
if(pos < l || r < pos) return;
if(l == r){
t3[node] = val;
return;
}
update3(pos, val, node*2, l, mid), update3(pos, val, node*2+1, mid+1, r);
t3[node] = t3[node*2] * t3[node*2+1] % mod;
}
ll find1(int nl, int nr, int node = 1, int l = 0, int r = n-1){
if(nr < l || r < nl) return 1;
if(nl <= l && r <= nr) return t1[node];
return min(INF, find1(nl, nr, node*2, l, mid) * find1(nl, nr, node*2+1, mid+1, r));
}
array<int, 2> find2(int nl, int nr, int node = 1, int l = 0, int r = n-1){
if(nr < l || r < nl) return {0, 0};
if(nl <= l && r <= nr) return t2[node];
return max(find2(nl, nr, node*2, l, mid), find2(nl, nr, node*2+1, mid+1, r));
}
ll find3(int nl, int nr, int node = 1, int l = 0, int r = n-1){
if(nr < l || r < nl) return 1;
if(nl <= l && r <= nr) return t3[node];
return find3(nl, nr, node*2, l, mid) * find3(nl, nr, node*2+1, mid+1, r) % mod;
}
int find_max(int l, int r){
if(l == r) return r;
ll k = x[r] * y[r];
auto mx = find2(l, r-1);
for(int i=l;i<r;i++) assert(x[i] == 1);
return k > mx[0] ? r : mx[1];
}
int solve(){
auto it = s.rbegin();
int mx = find_max(*prev(it)+1, *it);
// for(int k=n-1;k<n;k++){
// assert(y[mx] >= find1(mx+1, k) * y[k]);
// }
for(int k=mx-1;k>=0;k--){
if(y[k] > find1(k+1, mx) * y[mx]) mx = k;
}
return find3(0, mx) * y[mx] % mod;
}
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];
s.insert(-1);
for(int i=0;i<N;i++) if(x[i] > 1) s.insert(i);
s.insert(N-1);
build1(), build2(), build3();
return solve();
}
int updateX(int pos, int val) {
if(pos < n-1 && x[pos] > 1) s.erase(pos);
x[pos] = val, update1(pos, val), update3(pos, val);
if(x[pos] > 1) s.insert(pos);
return solve();
}
int updateY(int pos, int val) {
y[pos] = val, update2(pos, val);
return solve();
}
Compilation message
horses.cpp: In function 'int solve()':
horses.cpp:98:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
98 | return find3(0, mx) * y[mx] % mod;
| ~~~~~~~~~~~~~~~~~~~~~^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
224 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 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 |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Runtime error |
2 ms |
464 KB |
Execution killed with signal 6 |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1572 ms |
56156 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
312 KB |
Output is correct |
12 |
Correct |
1 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
308 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
312 KB |
Output is correct |
21 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
22 |
Halted |
0 ms |
0 KB |
- |