oj.uz

Submission #478515

# Submission time Handle Problem Language Result Execution time Memory
478515 2021-10-07T20:23:39 Z KULIKOLD Game (IOI13_game) C++17
80 / 100
 13000 ms 211928 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 = 300;
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 256 KB Output is correct
3 Correct 1 ms 292 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 0 ms 204 KB Output is correct
9 Correct 1 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 0 ms 204 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 0 ms 204 KB Output is correct
4 Correct 1166 ms 9744 KB Output is correct
5 Correct 1014 ms 10040 KB Output is correct
6 Correct 1366 ms 7228 KB Output is correct
7 Correct 1099 ms 6792 KB Output is correct
8 Correct 734 ms 4564 KB Output is correct
9 Correct 1206 ms 6980 KB Output is correct
10 Correct 1065 ms 6556 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 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 2579 ms 22352 KB Output is correct
13 Correct 2282 ms 10064 KB Output is correct
14 Correct 372 ms 836 KB Output is correct
15 Correct 2751 ms 14368 KB Output is correct
16 Correct 3017 ms 29360 KB Output is correct
17 Correct 1598 ms 14760 KB Output is correct
18 Correct 4494 ms 29744 KB Output is correct
19 Correct 4127 ms 29944 KB Output is correct
20 Correct 4082 ms 29204 KB Output is correct
21 Correct 1 ms 296 KB Output is correct

Subtask #4
17.0 / 17.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 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 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 1177 ms 9616 KB Output is correct
13 Correct 955 ms 10152 KB Output is correct
14 Correct 1286 ms 7096 KB Output is correct
15 Correct 1096 ms 6852 KB Output is correct
16 Correct 712 ms 4592 KB Output is correct
17 Correct 1185 ms 7040 KB Output is correct
18 Correct 1125 ms 6548 KB Output is correct
19 Correct 2566 ms 22524 KB Output is correct
20 Correct 2234 ms 10032 KB Output is correct
21 Correct 382 ms 944 KB Output is correct
22 Correct 2836 ms 14312 KB Output is correct
23 Correct 3225 ms 29340 KB Output is correct
24 Correct 1658 ms 14756 KB Output is correct
25 Correct 4419 ms 29656 KB Output is correct
26 Correct 3989 ms 29896 KB Output is correct
27 Correct 4082 ms 29284 KB Output is correct
28 Correct 2666 ms 51424 KB Output is correct
29 Correct 5019 ms 83904 KB Output is correct
30 Correct 4400 ms 42376 KB Output is correct
31 Correct 3183 ms 29256 KB Output is correct
32 Correct 396 ms 10036 KB Output is correct
33 Correct 674 ms 10460 KB Output is correct
34 Correct 4668 ms 77460 KB Output is correct
35 Correct 2047 ms 35028 KB Output is correct
36 Correct 6734 ms 81200 KB Output is correct
37 Correct 6183 ms 81712 KB Output is correct
38 Correct 5935 ms 81180 KB Output is correct
39 Correct 3661 ms 57168 KB Output is correct
40 Correct 0 ms 208 KB Output is correct

Subtask #5
0 / 20.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 0 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 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 1123 ms 9692 KB Output is correct
13 Correct 955 ms 10072 KB Output is correct
14 Correct 1299 ms 7096 KB Output is correct
15 Correct 1033 ms 6868 KB Output is correct
16 Correct 717 ms 4568 KB Output is correct
17 Correct 1124 ms 6920 KB Output is correct
18 Correct 1063 ms 6564 KB Output is correct
19 Correct 2529 ms 22432 KB Output is correct
20 Correct 2240 ms 10020 KB Output is correct
21 Correct 360 ms 964 KB Output is correct
22 Correct 2664 ms 14348 KB Output is correct
23 Correct 2901 ms 29060 KB Output is correct
24 Correct 1581 ms 14632 KB Output is correct
25 Correct 4341 ms 29376 KB Output is correct
26 Correct 4011 ms 29604 KB Output is correct
27 Correct 4022 ms 29076 KB Output is correct
28 Correct 2611 ms 51368 KB Output is correct
29 Correct 4940 ms 84056 KB Output is correct
30 Correct 4330 ms 42532 KB Output is correct
31 Correct 3061 ms 29468 KB Output is correct
32 Correct 397 ms 10216 KB Output is correct
33 Correct 632 ms 10308 KB Output is correct
34 Correct 4587 ms 77580 KB Output is correct
35 Correct 1947 ms 34976 KB Output is correct
36 Correct 6721 ms 81460 KB Output is correct
37 Correct 6157 ms 81664 KB Output is correct
38 Correct 5996 ms 81232 KB Output is correct
39 Correct 12374 ms 211928 KB Output is correct
40 Execution timed out 13024 ms 152496 KB Time limit exceeded
41 Halted 0 ms 0 KB -