Submission #478519

#	Time	Username	Problem	Language	Result	Execution time	Memory
478519		KULIKOLD	Game (IOI13_game)	C++17	100 / 100	8426 ms	110808 KiB

game

#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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20