제출 #477782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477782		andrey27_sm	게임 (IOI13_game)	C++17	63 / 100	1556 ms	256004 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int c, rl;

ll gcd(ll x,ll y){
    if(x == 0 or y == 0) return max(x,y);
    return __gcd(x,y);
}
struct Node{
    Node* lS;
    Node* rS;
    int l, r, m;
    ll val;
    ll tmp_val;
    Node(){
        val = 0;
        lS = nullptr;
        rS = nullptr;
        l = 0;
        r = 0;
        m = 0;
    }
    Node(int l1,int r1){
        val = 0;
        lS = nullptr;
        rS = nullptr;
        l = l1;
        r = r1;
        m = (l+r)/2;
    }
    ll get(int tl,int tr){
        if(tl <= l and r <= tr) return val;
        if(tr <= m){
            if(lS) return lS->get(tl,tr);
            return 0;
        }
        else if(tl > m){
            if(rS) return rS->get(tl,tr);
            return 0;
        }else{
            tmp_val = 0;
            if(lS) tmp_val = lS->get(tl,m);
            if(rS) tmp_val = gcd(tmp_val,(rS->get(m,tr)));
            return tmp_val;
        }
    }
    void update(int y,ll vals){
        if(l == r) {
            val = vals;
            return;
        }
        if(y <= m){
            if(!lS) lS = new Node(l,m);
            lS->update(y,vals);
        }
        if(y > m){
            if(!rS) rS = new Node(m+1,r);
            rS->update(y,vals);
        }
        val = 0;
        if(lS) val = lS->val;
        if(rS) val = gcd(val,rS->val);
    }
};

struct Node2{
    Node2 *lS;
    Node2 *rS;
    Node *root;
    int l,r,m;
    ll tmp_val;
    Node2(){
        lS = nullptr;
        rS = nullptr;
        l = r = 0;
        root = new Node(0,c);
    }
    Node2(int l1,int r1){
        lS = nullptr;
        rS = nullptr;
        l = l1;
        r = r1;
        m = (l+r)/2;
        root = new Node(0,c);
    }
    ll get(int x1,int x2,int y1,int y2){
        if(x1 <= l and r <= x2) return root->get(y1,y2);
        if(x2 <= m){
            if(lS) return lS->get(x1,x2,y1,y2);
            return 0;
        }
        else if(x1 > m){
            if(rS) return rS->get(x1,x2,y1,y2);
            return 0;
        }else{
            tmp_val = 0;
            if(lS) tmp_val = lS->get(x1,m,y1,y2);
            if(rS) tmp_val = gcd(tmp_val,(rS->get(m+1,x2,y1,y2)));
            return tmp_val;
        }
    }
    void update(int x,int y,ll vals){
        if(l == r){
            root->update(y,vals);
            return;
        }
        if(x <= m){
            if(!lS) lS = new Node2(l,m);
            lS->update(x,y,vals);
        }
        if(x > m){
            if(!rS) rS = new Node2(m+1,r);
            rS->update(x,y,vals);
        }
        tmp_val = 0;
        if(lS) tmp_val = lS->root->get(y,y);
        if(rS) tmp_val = gcd(tmp_val,rS->root->get(y,y));
        root->update(y,tmp_val);
    }

};

Node2 *root = nullptr;
void init(int R,int C){
    rl = R-1;
    c = C-1;
    root = new Node2(0,rl);
}
void update(int P,int Q,ll K){
    root->update(P,Q,K);
}
ll calculate(int P,int Q,int U,int V){
    return root->get(P,U,Q,V);
}
/*
int main(){
    int t1,t2,t3;
    cin >> t1 >> t2 >> t3;
    init(t1,t2);
    while (t3--){
        int type;
        cin >> type;
        if(type == 1){
            int x,y;
            ll val;
            cin >> x >> y >> val;
            update(x,y,val);
        }
        if(type == 2){
            int x1,y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << calculate(x1,y1,x2,y2) << "\n";
        }
    }
    return 0;
}*/

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20