oj.uz

Submission #478518

# Submission time Handle Problem Language Result Execution time Memory
478518 2021-10-07T20:32:51 Z KULIKOLD Game (IOI13_game) C++17
100 / 100
 8714 ms 134948 KB 
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> super_set;
int c, rl;
struct Node{
    Node* lS;
    Node* rS;
    ll val;
    Node(){
        val = 0;
        lS = nullptr;
        rS = nullptr;
    }
};
ll gcd(ll x,ll y){
    if(x == 0 or y == 0) return max(x,y);
    return __gcd(x,y);
}
ll get_val(Node *v){
    if(v == nullptr) return 0;
    return v->val;
}
struct NodeST{
    Node root;
    void del(Node *v){
        if (v==nullptr)
            return;
        del(v->lS);
        del(v->rS);
        delete v;
    }
    void del(){
        del(root.lS);
        del(root.rS);
    }
    void update(Node* v,int l,int r,int t,ll val){
        if (l == r){
            (v->val) = val;
            return;
        }
        ll m = (l+r)/2;
        if (t <= m){
            if (v->lS == nullptr) v->lS = new Node();
            update(v->lS,l,m,t,val);
        }else{
            if (v->rS == nullptr) v->rS = new Node();
            update(v->rS,m+1,r,t,val);
        }
        v->val = gcd(get_val(v->lS),get_val(v->rS));
    }
    ll get(Node *v,int l,int r,int tl,int tr){
        if(v == nullptr or r < tl or tr < l) return 0;
        if(tl <= l and r <= tr) {
            return v->val;
        }
        ll m = (l+r)/2;
        return gcd(get(v->rS,m+1,r,tl,tr),get(v->lS,l,m,tl,tr));
    }
    void update(ll t,ll val){
        return update(&root,0,c,t,val);
    }
    ll get(ll tl,ll tr){
        return get(&root,0,c,tl,tr);
    }
    NodeST(){
        root = *new Node();
    }
};
struct Node2{
    Node2 *lS;
    Node2 *rS;
    NodeST val;
    Node2(){
        lS = nullptr;
        rS = nullptr;
        val = *new NodeST();
    }
};

void del(Node2 *v){
    if (v==nullptr)
        return;
    del(v->lS);
    del(v->rS);
    (v->val).del();
    delete v;
}
void update(Node2* v,int l,int r,int x,int y,ll val){
    if (l == r){
        (v->val).update(y,val);
        return;
    }
    ll m = (l+r)/2;
    if (x <= m){
        if (v->lS == nullptr) v->lS = new Node2();
        update(v->lS,l,m,x,y,val);
    }else{
        if (v->rS == nullptr) v->rS = new Node2();
        update(v->rS,m+1,r,x,y,val);
    }
    ll new_val = 0;
    if(v->lS) new_val=gcd(new_val,(v->lS)->val.get(y,y));
    if(v->rS) new_val=gcd(new_val,(v->rS)->val.get(y,y));
    v->val.update(y,new_val);
}
ll get(Node2 *v,int l,int r,int xl,int xr,int yl,int yr){
    if(v == nullptr or r < xl or xr < l) return 0;
    if(xl <= l and r <= xr) {
        return (v->val).get(yl,yr);
    }
    ll m = (l+r)/2;
    return gcd(get(v->lS,l,m,xl,xr,yl,yr),get(v->rS,m+1,r,xl,xr,yl,yr));
}
Node2 root;
const int SQRT = 1500;
map<pair<int,int>,ll> buf,all;
super_set X,Y;
void updates(int x,int y,ll val){
    if (all.count({x,y})){
        update(&root,0,rl,X.order_of_key(x),Y.order_of_key(y),val);
        all[{x,y}] = val;
        return;
    }
    buf[{x,y}] = val;
    if (buf.size()>SQRT){
        del(root.lS);
        del(root.rS);
        root.lS = nullptr;
        root.rS = nullptr;
        for(auto [cord,val]:buf){
            X.insert(cord.first);
            Y.insert(cord.second);
            all[cord] = val;
        }
        buf.clear();
        rl = X.size();
        c = Y.size();
        for(auto [cord,val]:all){
            update(&root,0,rl,X.order_of_key(cord.first),Y.order_of_key(cord.second),val);
        }

    }
}
ll get(int xl,int xr,int yl,int yr){
    ll ret = 0;
    for(auto [cord,val]:buf){
        if (xl<=cord.first && cord.first<=xr && yl<=cord.second && cord.second<=yr)
            ret = __gcd(ret,val);
    }
    return __gcd(ret,get(&root,0,rl,X.order_of_key(xl),X.order_of_key(xr+1)-1,Y.order_of_key(yl),Y.order_of_key(yr+1)-1));
}


/*
int main() {
    int R,C,n;
    cin >> R >> C >> n;
    rl = -1;
    c = -1;
    for (int i = 0; i < n; ++i) {
        int type  = 0;
        cin >> type;
        if(type == 1){
            int x,y,t;
            cin >> x >> y >> t;
            updates(x,y,t);
        }
        else{
            int x1,x2,y1,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << get(x1,x2,y1,y2) << "\n";
        }
    }
    return 0;
}
*/
void init(int R,int C){
    rl = -1;
    c = -1;
    root = *new Node2();
}
void update(int P,int Q,ll K){
    updates(P,Q,K);
}
ll calculate(int P,int Q,int U,int V){
    return get(P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 280 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2519 ms 9696 KB Output is correct
5 Correct 2215 ms 9868 KB Output is correct
6 Correct 2450 ms 6872 KB Output is correct
7 Correct 3304 ms 6628 KB Output is correct
8 Correct 1993 ms 4784 KB Output is correct
9 Correct 2955 ms 6472 KB Output is correct
10 Correct 3025 ms 6236 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 3026 ms 17268 KB Output is correct
13 Correct 3764 ms 6992 KB Output is correct
14 Correct 895 ms 964 KB Output is correct
15 Correct 4380 ms 9324 KB Output is correct
16 Correct 5562 ms 20188 KB Output is correct
17 Correct 2700 ms 12224 KB Output is correct
18 Correct 4278 ms 20252 KB Output is correct
19 Correct 3600 ms 20372 KB Output is correct
20 Correct 3511 ms 19788 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 2549 ms 9628 KB Output is correct
13 Correct 2213 ms 9948 KB Output is correct
14 Correct 2452 ms 6948 KB Output is correct
15 Correct 3230 ms 6424 KB Output is correct
16 Correct 2058 ms 4696 KB Output is correct
17 Correct 2898 ms 6724 KB Output is correct
18 Correct 2983 ms 6516 KB Output is correct
19 Correct 2992 ms 17104 KB Output is correct
20 Correct 3805 ms 7068 KB Output is correct
21 Correct 924 ms 944 KB Output is correct
22 Correct 4345 ms 9220 KB Output is correct
23 Correct 5601 ms 19896 KB Output is correct
24 Correct 2639 ms 12248 KB Output is correct
25 Correct 4264 ms 20212 KB Output is correct
26 Correct 3546 ms 20396 KB Output is correct
27 Correct 3563 ms 19756 KB Output is correct
28 Correct 2240 ms 23372 KB Output is correct
29 Correct 3605 ms 43596 KB Output is correct
30 Correct 4783 ms 19968 KB Output is correct
31 Correct 5098 ms 12788 KB Output is correct
32 Correct 916 ms 964 KB Output is correct
33 Correct 2005 ms 1224 KB Output is correct
34 Correct 5949 ms 40576 KB Output is correct
35 Correct 2775 ms 17888 KB Output is correct
36 Correct 5311 ms 40452 KB Output is correct
37 Correct 4123 ms 40872 KB Output is correct
38 Correct 4009 ms 40480 KB Output is correct
39 Correct 3506 ms 33012 KB Output is correct
40 Correct 0 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 2555 ms 9672 KB Output is correct
13 Correct 2222 ms 9664 KB Output is correct
14 Correct 2436 ms 6688 KB Output is correct
15 Correct 3208 ms 6740 KB Output is correct
16 Correct 1969 ms 4556 KB Output is correct
17 Correct 2871 ms 6684 KB Output is correct
18 Correct 3046 ms 6204 KB Output is correct
19 Correct 2999 ms 17120 KB Output is correct
20 Correct 3704 ms 6836 KB Output is correct
21 Correct 928 ms 868 KB Output is correct
22 Correct 4412 ms 9336 KB Output is correct
23 Correct 5644 ms 19864 KB Output is correct
24 Correct 2726 ms 12104 KB Output is correct
25 Correct 4413 ms 20224 KB Output is correct
26 Correct 3582 ms 20460 KB Output is correct
27 Correct 3420 ms 19688 KB Output is correct
28 Correct 2179 ms 23436 KB Output is correct
29 Correct 3714 ms 43532 KB Output is correct
30 Correct 4767 ms 20016 KB Output is correct
31 Correct 5109 ms 12972 KB Output is correct
32 Correct 923 ms 1028 KB Output is correct
33 Correct 2005 ms 1052 KB Output is correct
34 Correct 5961 ms 40636 KB Output is correct
35 Correct 2767 ms 17972 KB Output is correct
36 Correct 5361 ms 40712 KB Output is correct
37 Correct 4119 ms 40940 KB Output is correct
38 Correct 4030 ms 40324 KB Output is correct
39 Correct 3844 ms 73140 KB Output is correct
40 Correct 6894 ms 126488 KB Output is correct
41 Correct 6786 ms 57924 KB Output is correct
42 Correct 6060 ms 36836 KB Output is correct
43 Correct 8714 ms 124152 KB Output is correct
44 Correct 2772 ms 1220 KB Output is correct
45 Correct 3517 ms 32904 KB Output is correct
46 Correct 7926 ms 123964 KB Output is correct
47 Correct 7975 ms 134948 KB Output is correct
48 Correct 8159 ms 133304 KB Output is correct
49 Correct 1 ms 208 KB Output is correct