# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
387163 |
2021-04-08T05:28:46 Z |
Keshi |
Horses (IOI15_horses) |
C++17 |
|
469 ms |
53104 KB |
//In the name of God
#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (id << 1 | 1)
ll n, x[maxn], y[maxn];
pll seg[maxn << 2];
void bld(ll id, ll s, ll e, ll f = -1){
if(f != -1 && (f < s || e <= f)) return;
if(e - s == 1){
seg[id] = Mp(x[s], x[s] * y[s]);
return;
}
ll mid = (s + e) >> 1;
bld(lc, s, mid, f);
bld(rc, mid, e, f);
seg[id] = Mp(seg[lc].F * seg[rc].F % mod, max(seg[lc].S, seg[lc].F * seg[rc].S));
return;
}
pll get(ll id, ll s, ll e, ll l, ll r){
if(r <= s || e <= l) return Mp(1, 0);
if(l <= s && e <= r) return seg[id];
ll mid = (s + e) >> 1;
pll p1 = get(lc, s, mid, l, r);
pll p2 = get(rc, mid, e, l, r);
return Mp(p1.F * p2.F % mod, max(p1.S, p1.F * p2.S));
}
set<ll> st;
int solve(){
auto it = st.begin();
ll p = 1;
ll r = -1;
while(it != st.end()){
p *= x[-*it];
if(p >= mod){
r = -*it;
break;
}
it++;
}
pll c = get(1, 0, n, r + 1, n);
if(r != -1) c.S = max(c.S, y[r]);
c.S %= mod;
pll d = get(1, 0, n, 0, r + 1);
return d.F * c.S % mod;
}
int init(int N, int X[], int Y[]) {
n = N;
for(ll i = 0; i < n; i++){
x[i] = X[i];
y[i] = Y[i];
if(x[i] > 1){
st.insert(-i);
}
}
bld(1, 0, n);
return solve();
}
int updateX(int pos, int val){
if(x[pos] > 1) st.erase(-pos);
x[pos] = val;
if(x[pos] > 1) st.insert(-pos);
bld(1, 0, n, pos);
return solve();
}
int updateY(int pos, int val){
y[pos] = val;
bld(1, 0, n, pos);
return solve();
}
/*int main(){
fast_io;
return 0;
}*/
Compilation message
horses.cpp: In function 'int solve()':
horses.cpp:67:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
67 | return d.F * c.S % mod;
| ~~~~~~~~~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
2 ms |
364 KB |
Output is correct |
24 |
Correct |
2 ms |
364 KB |
Output is correct |
25 |
Correct |
2 ms |
492 KB |
Output is correct |
26 |
Correct |
2 ms |
492 KB |
Output is correct |
27 |
Correct |
2 ms |
364 KB |
Output is correct |
28 |
Correct |
2 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
2 ms |
492 KB |
Output is correct |
31 |
Correct |
2 ms |
364 KB |
Output is correct |
32 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
52972 KB |
Output is correct |
2 |
Correct |
412 ms |
53024 KB |
Output is correct |
3 |
Correct |
375 ms |
53104 KB |
Output is correct |
4 |
Correct |
469 ms |
53100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
2 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
2 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
2 ms |
364 KB |
Output is correct |
24 |
Correct |
2 ms |
364 KB |
Output is correct |
25 |
Correct |
2 ms |
492 KB |
Output is correct |
26 |
Correct |
3 ms |
492 KB |
Output is correct |
27 |
Correct |
2 ms |
492 KB |
Output is correct |
28 |
Correct |
2 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
492 KB |
Output is correct |
31 |
Correct |
2 ms |
364 KB |
Output is correct |
32 |
Correct |
2 ms |
364 KB |
Output is correct |
33 |
Correct |
55 ms |
28652 KB |
Output is correct |
34 |
Correct |
56 ms |
28780 KB |
Output is correct |
35 |
Correct |
198 ms |
52204 KB |
Output is correct |
36 |
Correct |
193 ms |
52204 KB |
Output is correct |
37 |
Correct |
52 ms |
28652 KB |
Output is correct |
38 |
Correct |
102 ms |
40556 KB |
Output is correct |
39 |
Correct |
37 ms |
28524 KB |
Output is correct |
40 |
Correct |
175 ms |
52076 KB |
Output is correct |
41 |
Correct |
37 ms |
28652 KB |
Output is correct |
42 |
Correct |
43 ms |
28652 KB |
Output is correct |
43 |
Correct |
165 ms |
51948 KB |
Output is correct |
44 |
Correct |
163 ms |
51948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
2 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
2 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
3 ms |
364 KB |
Output is correct |
24 |
Correct |
2 ms |
364 KB |
Output is correct |
25 |
Correct |
2 ms |
492 KB |
Output is correct |
26 |
Correct |
2 ms |
492 KB |
Output is correct |
27 |
Correct |
2 ms |
364 KB |
Output is correct |
28 |
Correct |
2 ms |
492 KB |
Output is correct |
29 |
Correct |
2 ms |
364 KB |
Output is correct |
30 |
Correct |
2 ms |
492 KB |
Output is correct |
31 |
Correct |
2 ms |
364 KB |
Output is correct |
32 |
Correct |
2 ms |
364 KB |
Output is correct |
33 |
Correct |
262 ms |
53100 KB |
Output is correct |
34 |
Correct |
404 ms |
53100 KB |
Output is correct |
35 |
Correct |
387 ms |
52992 KB |
Output is correct |
36 |
Correct |
458 ms |
52972 KB |
Output is correct |
37 |
Correct |
55 ms |
28908 KB |
Output is correct |
38 |
Correct |
57 ms |
28652 KB |
Output is correct |
39 |
Correct |
196 ms |
52204 KB |
Output is correct |
40 |
Correct |
191 ms |
52076 KB |
Output is correct |
41 |
Correct |
49 ms |
28652 KB |
Output is correct |
42 |
Correct |
101 ms |
40556 KB |
Output is correct |
43 |
Correct |
38 ms |
28524 KB |
Output is correct |
44 |
Correct |
171 ms |
52076 KB |
Output is correct |
45 |
Correct |
37 ms |
28524 KB |
Output is correct |
46 |
Correct |
42 ms |
28652 KB |
Output is correct |
47 |
Correct |
163 ms |
52076 KB |
Output is correct |
48 |
Correct |
166 ms |
51948 KB |
Output is correct |
49 |
Correct |
194 ms |
30676 KB |
Output is correct |
50 |
Correct |
203 ms |
30656 KB |
Output is correct |
51 |
Correct |
301 ms |
52960 KB |
Output is correct |
52 |
Correct |
290 ms |
52972 KB |
Output is correct |
53 |
Correct |
208 ms |
30572 KB |
Output is correct |
54 |
Correct |
225 ms |
43628 KB |
Output is correct |
55 |
Correct |
85 ms |
28652 KB |
Output is correct |
56 |
Correct |
293 ms |
52972 KB |
Output is correct |
57 |
Correct |
88 ms |
29548 KB |
Output is correct |
58 |
Correct |
144 ms |
29548 KB |
Output is correct |
59 |
Correct |
184 ms |
52076 KB |
Output is correct |