oj.uz

Submission #478708

# Submission time Handle Problem Language Result Execution time Memory
478708 2021-10-08T07:32:42 Z KULIKOLD Game (IOI13_game) C++17
10 / 100
 13000 ms 4448 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 = 220000;
    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 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 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 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
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 1 ms 204 KB Output is correct
4 Execution timed out 13039 ms 4384 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
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 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 Execution timed out 13091 ms 4448 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
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 300 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 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 Execution timed out 13046 ms 4204 KB Time limit exceeded
13 Halted 0 ms 0 KB -

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 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 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Execution timed out 13047 ms 4260 KB Time limit exceeded
13 Halted 0 ms 0 KB -