oj.uz

Submission #583570

# Submission time Handle Problem Language Result Execution time Memory
583570 2022-06-25T15:38:15 Z thomas_li Game (IOI13_game) C++17
100 / 100
 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);
}

Subtask #1
10.0 / 10.0

# 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

Subtask #2
27.0 / 27.0

# 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

Subtask #3
26.0 / 26.0

# 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

Subtask #4
17.0 / 17.0

# 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

Subtask #5
20.0 / 20.0

# 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