oj.uz

Submission #478511

# Submission time Handle Problem Language Result Execution time Memory
478511 2021-10-07T20:04:50 Z KULIKOLD Game (IOI13_game) C++17
63 / 100
 7335 ms 256004 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 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 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 = 150;
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){
        for(auto [cord,val]:all){
            update(&root,0,rl,X.order_of_key(cord.first),Y.order_of_key(cord.second),0);
        }
        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 268 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 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 1 ms 204 KB Output is correct
4 Correct 1863 ms 14464 KB Output is correct
5 Correct 1747 ms 15116 KB Output is correct
6 Correct 2364 ms 13164 KB Output is correct
7 Correct 2612 ms 12840 KB Output is correct
8 Correct 807 ms 7368 KB Output is correct
9 Correct 2428 ms 12912 KB Output is correct
10 Correct 2346 ms 12648 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 0 ms 204 KB Output is correct
2 Correct 1 ms 232 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 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 3904 ms 32924 KB Output is correct
13 Correct 2955 ms 15828 KB Output is correct
14 Correct 382 ms 1484 KB Output is correct
15 Correct 3411 ms 26120 KB Output is correct
16 Correct 5770 ms 80924 KB Output is correct
17 Correct 2326 ms 44656 KB Output is correct
18 Correct 7322 ms 76096 KB Output is correct
19 Correct 7119 ms 80636 KB Output is correct
20 Correct 6825 ms 82796 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #4
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 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 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 204 KB Output is correct
12 Correct 1788 ms 14560 KB Output is correct
13 Correct 1612 ms 15428 KB Output is correct
14 Correct 2279 ms 13140 KB Output is correct
15 Correct 2582 ms 12880 KB Output is correct
16 Correct 819 ms 7420 KB Output is correct
17 Correct 2533 ms 12940 KB Output is correct
18 Correct 2428 ms 12744 KB Output is correct
19 Correct 3925 ms 33336 KB Output is correct
20 Correct 2935 ms 16120 KB Output is correct
21 Correct 389 ms 1380 KB Output is correct
22 Correct 3398 ms 26180 KB Output is correct
23 Correct 5744 ms 80920 KB Output is correct
24 Correct 2277 ms 44616 KB Output is correct
25 Correct 7335 ms 75884 KB Output is correct
26 Correct 7147 ms 80696 KB Output is correct
27 Correct 6805 ms 83036 KB Output is correct
28 Correct 3014 ms 21188 KB Output is correct
29 Runtime error 6978 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
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 1 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 1838 ms 14548 KB Output is correct
13 Correct 1652 ms 14916 KB Output is correct
14 Correct 2330 ms 12756 KB Output is correct
15 Correct 2561 ms 12456 KB Output is correct
16 Correct 827 ms 6980 KB Output is correct
17 Correct 2449 ms 12800 KB Output is correct
18 Correct 2368 ms 12128 KB Output is correct
19 Correct 3958 ms 32880 KB Output is correct
20 Correct 2863 ms 15288 KB Output is correct
21 Correct 368 ms 1004 KB Output is correct
22 Correct 3374 ms 25760 KB Output is correct
23 Correct 5809 ms 80456 KB Output is correct
24 Correct 2323 ms 44188 KB Output is correct
25 Correct 7262 ms 75652 KB Output is correct
26 Correct 7142 ms 80284 KB Output is correct
27 Correct 6921 ms 82456 KB Output is correct
28 Correct 3037 ms 20768 KB Output is correct
29 Runtime error 6960 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -