oj.uz

Submission #478519

# Submission time Handle Problem Language Result Execution time Memory
478519 2021-10-07T20:40:07 Z KULIKOLD Game (IOI13_game) C++17
100 / 100
 8426 ms 110808 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 = 3000;
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 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 0 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 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 4855 ms 9420 KB Output is correct
5 Correct 4602 ms 9640 KB Output is correct
6 Correct 4774 ms 6800 KB Output is correct
7 Correct 3106 ms 6560 KB Output is correct
8 Correct 3597 ms 3712 KB Output is correct
9 Correct 3746 ms 6392 KB Output is correct
10 Correct 3210 ms 5908 KB Output is correct
11 Correct 1 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 0 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 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 5309 ms 16280 KB Output is correct
13 Correct 3774 ms 6468 KB Output is correct
14 Correct 950 ms 988 KB Output is correct
15 Correct 4399 ms 8440 KB Output is correct
16 Correct 5538 ms 18752 KB Output is correct
17 Correct 4207 ms 8468 KB Output is correct
18 Correct 4918 ms 19040 KB Output is correct
19 Correct 5291 ms 19136 KB Output is correct
20 Correct 5301 ms 18700 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 0 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 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 4635 ms 9376 KB Output is correct
13 Correct 4329 ms 9752 KB Output is correct
14 Correct 4449 ms 6644 KB Output is correct
15 Correct 3037 ms 6232 KB Output is correct
16 Correct 3493 ms 3756 KB Output is correct
17 Correct 3629 ms 6312 KB Output is correct
18 Correct 3145 ms 6124 KB Output is correct
19 Correct 5142 ms 16340 KB Output is correct
20 Correct 3692 ms 6468 KB Output is correct
21 Correct 945 ms 720 KB Output is correct
22 Correct 4395 ms 8420 KB Output is correct
23 Correct 5373 ms 18820 KB Output is correct
24 Correct 4082 ms 8480 KB Output is correct
25 Correct 4864 ms 19012 KB Output is correct
26 Correct 5435 ms 19436 KB Output is correct
27 Correct 5309 ms 18760 KB Output is correct
28 Correct 3481 ms 20420 KB Output is correct
29 Correct 5562 ms 40868 KB Output is correct
30 Correct 7133 ms 18556 KB Output is correct
31 Correct 4966 ms 12012 KB Output is correct
32 Correct 934 ms 800 KB Output is correct
33 Correct 1987 ms 964 KB Output is correct
34 Correct 5722 ms 37832 KB Output is correct
35 Correct 4332 ms 11412 KB Output is correct
36 Correct 5467 ms 38212 KB Output is correct
37 Correct 5642 ms 38340 KB Output is correct
38 Correct 5645 ms 37692 KB Output is correct
39 Correct 5156 ms 24088 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 1 ms 204 KB Output is correct
5 Correct 0 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 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 4648 ms 9584 KB Output is correct
13 Correct 4411 ms 9692 KB Output is correct
14 Correct 4401 ms 6472 KB Output is correct
15 Correct 3059 ms 6384 KB Output is correct
16 Correct 3432 ms 3852 KB Output is correct
17 Correct 3569 ms 6476 KB Output is correct
18 Correct 3081 ms 6240 KB Output is correct
19 Correct 5191 ms 16488 KB Output is correct
20 Correct 3672 ms 6708 KB Output is correct
21 Correct 902 ms 808 KB Output is correct
22 Correct 4333 ms 8608 KB Output is correct
23 Correct 5499 ms 18888 KB Output is correct
24 Correct 4050 ms 8784 KB Output is correct
25 Correct 4827 ms 19212 KB Output is correct
26 Correct 5223 ms 19488 KB Output is correct
27 Correct 5212 ms 18736 KB Output is correct
28 Correct 3394 ms 20552 KB Output is correct
29 Correct 5629 ms 40720 KB Output is correct
30 Correct 7237 ms 18492 KB Output is correct
31 Correct 5117 ms 11972 KB Output is correct
32 Correct 913 ms 836 KB Output is correct
33 Correct 2019 ms 1072 KB Output is correct
34 Correct 5773 ms 37828 KB Output is correct
35 Correct 4238 ms 11428 KB Output is correct
36 Correct 5560 ms 38088 KB Output is correct
37 Correct 5597 ms 38128 KB Output is correct
38 Correct 5678 ms 37744 KB Output is correct
39 Correct 4344 ms 58616 KB Output is correct
40 Correct 7871 ms 110808 KB Output is correct
41 Correct 8426 ms 49672 KB Output is correct
42 Correct 7768 ms 32172 KB Output is correct
43 Correct 7044 ms 108612 KB Output is correct
44 Correct 2676 ms 836 KB Output is correct
45 Correct 5030 ms 24116 KB Output is correct
46 Correct 8116 ms 109024 KB Output is correct
47 Correct 8137 ms 109296 KB Output is correct
48 Correct 8163 ms 108796 KB Output is correct
49 Correct 1 ms 204 KB Output is correct