# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
583570 |
2022-06-25T15:38:15 Z |
thomas_li |
Game (IOI13_game) |
C++17 |
|
9748 ms |
56940 KB |
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int MM = 1e6;
mt19937 rng(42069);
struct INode{ // 28 bytes
int c[2];
pair<int,int> pos; // y,x
int64_t g,v; int pri;
INode(int p, int q, int64_t k){
pos = {q,p};
g = v = k;
pri = rng();
c[0] = c[1] = 0;
}
INode(){
pos = {0,0};
g = v = pri = 0;
c[0] = c[1] = 0;
}
}ibuf[MM]; int ibuf_pos;
int64_t gcd(int64_t a, int64_t b) {
if (!a || !b)
return a | b;
auto shift = __builtin_ctzll(a | b);
a >>= __builtin_ctzll(a);
do {
b >>= __builtin_ctzll(b);
if (a > b)
swap(a, b);
b -= a;
} while (b);
return a << shift;
}
void upd(int u){
auto& cur = ibuf[u];
cur.g = cur.v;
if(cur.c[0]) cur.g = gcd(cur.g,ibuf[cur.c[0]].g);
if(cur.c[1]) cur.g = gcd(cur.g,ibuf[cur.c[1]].g);
}
int alloc(int p, int q, int64_t k){
auto& cur = ibuf[++ibuf_pos];
//cout << "creating new node: " << pos << " " << k << "\n";
cur = INode(p,q,k);
return ibuf_pos;
}
array<int,2> split(int u, pair<int,int> q){
if(!u) return {0,0};
if(ibuf[u].pos >= q){
auto p = split(ibuf[u].c[0],q); ibuf[u].c[0] = p[1];
upd(u);
return {p[0],u};
} else{
auto p = split(ibuf[u].c[1],q); ibuf[u].c[1] = p[0];
upd(u);
return {u,p[1]};
}
}
int merge(int l, int r){
if(!l) return r;
if(!r) return l;
int u;
if(ibuf[l].pri > ibuf[r].pri) ibuf[l].c[1] = merge(ibuf[l].c[1],r),u = l;
else ibuf[r].c[0] = merge(l,ibuf[r].c[0]), u = r;
upd(u);
return u;
}
int ins(int rt, int p, int q, int64_t k){
auto[lft,tmp] = split(rt,{q,p});
auto[same,rit] = split(tmp,{q,p+1});
return merge(lft,merge(alloc(p,q,k),rit));
}
int64_t query_in(int& rt, int l, int r){
auto[lft,tmp] = split(rt,{l,0});
auto[in,rit] = split(tmp,{r+1,0});
auto ans = ibuf[in].g;
rt = merge(lft,merge(in,rit));
return ans;
}
struct Node{ // 16 bytes
int l,r; // index in buffer
int rt; // index in ibuf
}buf[MM*4];
int n,m,pos;
int alloc_out(){
Node& rt = buf[++pos];
rt.l = rt.r = 0; rt.rt = 0;
return pos;
}
void print(int u){
if(!u) return;
print(ibuf[u].c[0]);
cout << ibuf[u].v << " ";
print(ibuf[u].c[1]);
}
// update all nodes that contain p in first layer
void upd(int u, int l, int r, int p, int q, int64_t k){
//cout << "inserting to : " << l << " " << r << " " << p << " " << q << "\n";
buf[u].rt = ins(buf[u].rt,p,q,k);
//print(buf[u].rt); cout << "\n";
if(l == r) return;
int mid = (l+r)/2;
if(p <= mid){
if(!buf[u].l) buf[u].l = alloc_out();
upd(buf[u].l,l,mid,p,q,k);
} else{
if(!buf[u].r) buf[u].r = alloc_out();
upd(buf[u].r,mid+1,r,p,q,k);
}
}
int64_t query(int u, int l, int r, int l_out, int r_out, int l_in, int r_in){
if(l == l_out && r == r_out){
return query_in(buf[u].rt,l_in,r_in);
}
int mid = (l+r)/2;
if(r_out <= mid){
if(!buf[u].l) return 0;
return query(buf[u].l,l,mid,l_out,r_out,l_in,r_in);
} else if(l_out > mid){
if(!buf[u].r) return 0;
return query(buf[u].r,mid+1,r,l_out,r_out,l_in,r_in);
} else{
int64_t vl = buf[u].l == 0 ? 0 : query(buf[u].l,l,mid,l_out,mid,l_in,r_in);
int64_t vr = buf[u].r == 0 ? 0 : query(buf[u].r,mid+1,r,mid+1,r_out,l_in,r_in);
return gcd(vl,vr);
}
}
void init(int R, int C){
n = R, m = C; pos = ibuf_pos = 0;
alloc_out(); // make root
}
void update(int P, int Q, long long K){
upd(1,0,n-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V){
return query(1,0,n-1,P,U,Q,V);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
39452 KB |
Output is correct |
2 |
Correct |
19 ms |
39380 KB |
Output is correct |
3 |
Correct |
18 ms |
39372 KB |
Output is correct |
4 |
Correct |
17 ms |
39428 KB |
Output is correct |
5 |
Correct |
19 ms |
39452 KB |
Output is correct |
6 |
Correct |
20 ms |
39448 KB |
Output is correct |
7 |
Correct |
20 ms |
39448 KB |
Output is correct |
8 |
Correct |
18 ms |
39380 KB |
Output is correct |
9 |
Correct |
18 ms |
39424 KB |
Output is correct |
10 |
Correct |
18 ms |
39332 KB |
Output is correct |
11 |
Correct |
18 ms |
39408 KB |
Output is correct |
12 |
Correct |
18 ms |
39452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
39380 KB |
Output is correct |
2 |
Correct |
18 ms |
39380 KB |
Output is correct |
3 |
Correct |
19 ms |
39448 KB |
Output is correct |
4 |
Correct |
973 ms |
47812 KB |
Output is correct |
5 |
Correct |
450 ms |
47692 KB |
Output is correct |
6 |
Correct |
1868 ms |
45232 KB |
Output is correct |
7 |
Correct |
2213 ms |
44884 KB |
Output is correct |
8 |
Correct |
1436 ms |
45220 KB |
Output is correct |
9 |
Correct |
2235 ms |
44888 KB |
Output is correct |
10 |
Correct |
2197 ms |
44504 KB |
Output is correct |
11 |
Correct |
18 ms |
39380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
39380 KB |
Output is correct |
2 |
Correct |
21 ms |
39436 KB |
Output is correct |
3 |
Correct |
19 ms |
39380 KB |
Output is correct |
4 |
Correct |
19 ms |
39380 KB |
Output is correct |
5 |
Correct |
19 ms |
39344 KB |
Output is correct |
6 |
Correct |
20 ms |
39420 KB |
Output is correct |
7 |
Correct |
19 ms |
39384 KB |
Output is correct |
8 |
Correct |
21 ms |
39404 KB |
Output is correct |
9 |
Correct |
19 ms |
39416 KB |
Output is correct |
10 |
Correct |
19 ms |
39456 KB |
Output is correct |
11 |
Correct |
21 ms |
39400 KB |
Output is correct |
12 |
Correct |
1578 ms |
47700 KB |
Output is correct |
13 |
Correct |
4253 ms |
44088 KB |
Output is correct |
14 |
Correct |
770 ms |
44612 KB |
Output is correct |
15 |
Correct |
4777 ms |
44536 KB |
Output is correct |
16 |
Correct |
574 ms |
44364 KB |
Output is correct |
17 |
Correct |
2411 ms |
45640 KB |
Output is correct |
18 |
Correct |
4769 ms |
45936 KB |
Output is correct |
19 |
Correct |
3832 ms |
45956 KB |
Output is correct |
20 |
Correct |
4486 ms |
45628 KB |
Output is correct |
21 |
Correct |
19 ms |
39380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
39388 KB |
Output is correct |
2 |
Correct |
19 ms |
39408 KB |
Output is correct |
3 |
Correct |
19 ms |
39448 KB |
Output is correct |
4 |
Correct |
18 ms |
39452 KB |
Output is correct |
5 |
Correct |
19 ms |
39360 KB |
Output is correct |
6 |
Correct |
18 ms |
39380 KB |
Output is correct |
7 |
Correct |
19 ms |
39388 KB |
Output is correct |
8 |
Correct |
19 ms |
39456 KB |
Output is correct |
9 |
Correct |
19 ms |
39420 KB |
Output is correct |
10 |
Correct |
22 ms |
39440 KB |
Output is correct |
11 |
Correct |
19 ms |
39452 KB |
Output is correct |
12 |
Correct |
966 ms |
47976 KB |
Output is correct |
13 |
Correct |
428 ms |
47608 KB |
Output is correct |
14 |
Correct |
1844 ms |
45296 KB |
Output is correct |
15 |
Correct |
2112 ms |
44972 KB |
Output is correct |
16 |
Correct |
1361 ms |
45260 KB |
Output is correct |
17 |
Correct |
2052 ms |
44912 KB |
Output is correct |
18 |
Correct |
2196 ms |
44548 KB |
Output is correct |
19 |
Correct |
1635 ms |
47620 KB |
Output is correct |
20 |
Correct |
4238 ms |
43980 KB |
Output is correct |
21 |
Correct |
770 ms |
44760 KB |
Output is correct |
22 |
Correct |
4858 ms |
44632 KB |
Output is correct |
23 |
Correct |
586 ms |
44372 KB |
Output is correct |
24 |
Correct |
2412 ms |
45604 KB |
Output is correct |
25 |
Correct |
4267 ms |
45776 KB |
Output is correct |
26 |
Correct |
3588 ms |
45948 KB |
Output is correct |
27 |
Correct |
4387 ms |
45348 KB |
Output is correct |
28 |
Correct |
1324 ms |
52580 KB |
Output is correct |
29 |
Correct |
2129 ms |
55240 KB |
Output is correct |
30 |
Correct |
5879 ms |
48192 KB |
Output is correct |
31 |
Correct |
5052 ms |
48092 KB |
Output is correct |
32 |
Correct |
1006 ms |
49148 KB |
Output is correct |
33 |
Correct |
1468 ms |
49080 KB |
Output is correct |
34 |
Correct |
602 ms |
48972 KB |
Output is correct |
35 |
Correct |
2644 ms |
51712 KB |
Output is correct |
36 |
Correct |
5326 ms |
53136 KB |
Output is correct |
37 |
Correct |
4231 ms |
53428 KB |
Output is correct |
38 |
Correct |
5127 ms |
52948 KB |
Output is correct |
39 |
Correct |
3425 ms |
52596 KB |
Output is correct |
40 |
Correct |
20 ms |
39380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
39380 KB |
Output is correct |
2 |
Correct |
24 ms |
39380 KB |
Output is correct |
3 |
Correct |
24 ms |
39456 KB |
Output is correct |
4 |
Correct |
19 ms |
39380 KB |
Output is correct |
5 |
Correct |
19 ms |
39380 KB |
Output is correct |
6 |
Correct |
20 ms |
39408 KB |
Output is correct |
7 |
Correct |
18 ms |
39452 KB |
Output is correct |
8 |
Correct |
18 ms |
39448 KB |
Output is correct |
9 |
Correct |
19 ms |
39352 KB |
Output is correct |
10 |
Correct |
21 ms |
39380 KB |
Output is correct |
11 |
Correct |
17 ms |
39400 KB |
Output is correct |
12 |
Correct |
995 ms |
48000 KB |
Output is correct |
13 |
Correct |
461 ms |
47628 KB |
Output is correct |
14 |
Correct |
1813 ms |
45280 KB |
Output is correct |
15 |
Correct |
2127 ms |
45020 KB |
Output is correct |
16 |
Correct |
1350 ms |
45260 KB |
Output is correct |
17 |
Correct |
2041 ms |
44976 KB |
Output is correct |
18 |
Correct |
2244 ms |
44656 KB |
Output is correct |
19 |
Correct |
1620 ms |
47636 KB |
Output is correct |
20 |
Correct |
4321 ms |
44212 KB |
Output is correct |
21 |
Correct |
782 ms |
44620 KB |
Output is correct |
22 |
Correct |
4907 ms |
44844 KB |
Output is correct |
23 |
Correct |
584 ms |
44312 KB |
Output is correct |
24 |
Correct |
2494 ms |
45556 KB |
Output is correct |
25 |
Correct |
4555 ms |
45968 KB |
Output is correct |
26 |
Correct |
3630 ms |
45880 KB |
Output is correct |
27 |
Correct |
4480 ms |
45564 KB |
Output is correct |
28 |
Correct |
1311 ms |
52860 KB |
Output is correct |
29 |
Correct |
2005 ms |
55376 KB |
Output is correct |
30 |
Correct |
5932 ms |
48116 KB |
Output is correct |
31 |
Correct |
5138 ms |
47988 KB |
Output is correct |
32 |
Correct |
1014 ms |
49320 KB |
Output is correct |
33 |
Correct |
1539 ms |
49148 KB |
Output is correct |
34 |
Correct |
624 ms |
49100 KB |
Output is correct |
35 |
Correct |
2645 ms |
51692 KB |
Output is correct |
36 |
Correct |
6300 ms |
53056 KB |
Output is correct |
37 |
Correct |
4612 ms |
53368 KB |
Output is correct |
38 |
Correct |
5273 ms |
52828 KB |
Output is correct |
39 |
Correct |
2045 ms |
54828 KB |
Output is correct |
40 |
Correct |
3491 ms |
56940 KB |
Output is correct |
41 |
Correct |
9748 ms |
49712 KB |
Output is correct |
42 |
Correct |
8473 ms |
49092 KB |
Output is correct |
43 |
Correct |
1131 ms |
51720 KB |
Output is correct |
44 |
Correct |
1915 ms |
49588 KB |
Output is correct |
45 |
Correct |
3343 ms |
52572 KB |
Output is correct |
46 |
Correct |
6775 ms |
55772 KB |
Output is correct |
47 |
Correct |
6094 ms |
55692 KB |
Output is correct |
48 |
Correct |
7635 ms |
55444 KB |
Output is correct |
49 |
Correct |
20 ms |
39456 KB |
Output is correct |