Submission #825803

#	Time	Username	Problem	Language	Result	Execution time	Memory
825803		79brue	Game (IOI13_game)	C++17	100 / 100	3210 ms	175452 KiB

game

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

using namespace std;

typedef long long ll;

int n, m;

struct segTree1d{
    struct Node{
        Node *lc, *rc;
        ll val; int loc; /// loc: 걸어둔 정점이면 그 위치, 아니면 0

        Node(){
            lc = rc = nullptr;
            val = 0, loc = -1;
        }

        ~Node(){
            if(lc) delete lc;
            if(rc) delete rc;
        }

        void update(int l, int r, int x, ll v){
            if(loc != -1){
                int m = (l+r)>>1;
                if(loc <= m) lc = new Node(), lc->update(l, m, loc, val);
                else rc = new Node(), rc->update(m+1, r, loc, val);
                loc = -1;
                val = __gcd(lc?lc->val:0, rc?rc->val:0);
            }
            if(l==r){
                val = v;
                return;
            }
            if(!val && !lc && !rc){
                val = v, loc = x;
                return;
            }
            int m = (l+r)>>1;
            if(x<=m){
                if(!lc) lc = new Node();
                lc->update(l, m, x, v);
            }
            else{
                if(!rc) rc = new Node();
                rc->update(m+1, r, x, v);
            }
            val = __gcd(lc?lc->val:0, rc?rc->val:0);
        }

        ll query(int l, int r, int s, int e){
            if(loc != -1){
                if(loc < s || e < loc) return 0;
                else return val;
            }
            if(r<s || e<l) return 0;
            if(s<=l && r<=e) return val;
            int m = (l+r)>>1;
            return __gcd(lc ? lc->query(l, m, s, e) : 0, rc ? rc->query(m+1, r, s, e) : 0);
        }
    } *root;

    segTree1d(){
        root = new Node();
    }

    void update(int y, ll v){
        root->update(0, m-1, y, v);
    }

    ll query(int yl, int yr){
        return root->query(0, m-1, yl, yr);
    }
};

struct segTree2d{
    struct Node{
        Node *lc, *rc;
        segTree1d tree;

        Node(){
            lc = rc = nullptr;
            tree = segTree1d();
        }

        ~Node(){
            if(lc) delete lc;
            if(rc) delete rc;
        }

        void update(int l, int r, int x, int y, ll v){
            if(l==r){
                tree.update(y, v);
                return;
            }
            int m = (l+r)>>1;
            if(x<=m){
                if(!lc) lc = new Node();
                lc->update(l, m, x, y, v);
                tree.update(y, __gcd(lc->tree.query(y, y), rc ? rc->tree.query(y, y) : 0));
            }
            else{
                if(!rc) rc = new Node();
                rc->update(m+1, r, x, y, v);
                tree.update(y, __gcd(rc->tree.query(y, y), lc ? lc->tree.query(y, y) : 0));
            }
        }

        ll query(int l, int r, int s, int e, int ys, int ye){
            if(r<s || e<l) return 0;
            if(s<=l && r<=e) return tree.query(ys, ye);
            int m = (l+r)>>1;
            return __gcd(lc ? lc->query(l, m, s, e, ys, ye) : 0, rc ? rc->query(m+1, r, s, e, ys, ye) : 0);
        }
    } *root;

    segTree2d(){
        root = new Node();
    }

    void update(int x, int y, ll v){
        root->update(0, n-1, x, y, v);
    }

    ll query(int xs, int xe, int ys, int ye){
        return root->query(0, n-1, xs, xe, ys, ye);
    }
} tree;

void init(int R, int C){
    n = R, m = C;
}

void update(int P, int Q, ll K) {
    tree.update(P, Q, K);
}

ll calculate(int P, int Q, int U, int V){
    return tree.query(P, U, Q, V);
}

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