제출 #962748

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

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn =  2048;
typedef long long ll;
int n, m;
long long a[maxn][maxn];

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct segtree2d{
    struct segtree{
        struct Node{
            Node *l, *r;
            long long key;
            Node(){
                key = 0;
                l = nullptr;
                r = nullptr;
            }
            Node(long long _key){
                key = _key;
                l = nullptr;
                r = nullptr;
            }
        };

        Node *root;
        segtree *ltree, *rtree;
        //long long key;
        segtree(){
            root = new Node();
            ltree = nullptr;
            rtree = nullptr;
            //key = 0;
        }

        inline void compute(Node *t){
            if (!t->l) t->l = new Node();
            if (!t->r) t->r = new Node();
            t->key = gcd2(t->l->key, t->r->key);
        }

        void update(Node *t, int l, int r, int pos, long long value){
            assert(t);
            //cerr << "update: " << t << " " << l << " " << r << " " << pos << " " << value << "\n";
            if (l == r){
                t->key = value;
                return;
            }
            int mid = (r - l) / 2 + l;
            if (pos <= mid){
                if (!t->l) t->l = new Node();
                update(t->l, l, mid, pos, value);
            }
            else{
                if (!t->r) t->r = new Node();
                update(t->r, mid + 1, r, pos, value);
            }
            compute(t);
        }

        inline void Update(int pos, long long value){
            update(root, 0, m - 1, pos, value);
        }

        long long query(Node *t, int l, int r, int ql, int qr){
            assert(t);
            if (t->key == 0) return 0;
            if (l == ql && r == qr) return t->key;
            int mid = (r - l) / 2 + l;
            if (qr <= mid){
                if (!t->l) return (long long) 0;
                //t->l = new Node();
                return query(t->l, l, mid, ql, qr);
            }
            if (ql > mid){
                if (!t->r) return (long long) 0;
                //t->r = new Node();
                return query(t->r, mid + 1, r, ql, qr);
            }
            long long gcdl, gcdr;
            /*if (!t->l) t->l = new Node();
            if (!t->r) t->r = new Node();*/
            gcdl = (t->l)? query(t->l, l, mid, ql, mid): (long long)0;
            gcdr = (t->r)? query(t->r, mid + 1, r, mid + 1, qr): (long long) 0;
            return gcd2(gcdl, gcdr);
        }

        long long Query(int ql, int qr){
            return query(root, 0, m - 1, ql, qr);
        }

    };

    segtree *root;
    segtree2d(){
        root = new segtree();
    }

    inline void compute(segtree *t, int posc){
        assert(t);
        if (!t->ltree) t->ltree = new segtree();
        if (!t->rtree) t->rtree = new segtree();
        //t->key = gcd2(t->ltree->key, t->rtree->key);
        long long lgcd = t->ltree->Query(posc, posc);
        long long rgcd = t->rtree->Query(posc, posc);
        long long value = gcd2(lgcd, rgcd);
        t->Update(posc, value);
    }

    void update(segtree *t, int l, int r, int posr, int posc, long long value){
        //cerr << "Update row tree: " << t << " " << l << " " << r << " " << posr << " " << posc << " " << value << "\n";
        assert(t);
        if (l == r){
            //cerr << "l == r is true. update locally\n";
            t->Update(posc, value);
            //cerr << "local update is done\n";
            return;
        }
        int mid = (r - l) / 2 + l;
        if (posr <= mid){
            if (!t->ltree) t->ltree = new segtree();
            update(t->ltree, l, mid, posr, posc, value);
        }
        else{
            if (!t->rtree) t->rtree = new segtree();
            update(t->rtree, mid + 1, r, posr, posc, value);
        }
        compute(t, posc);
    }

    void Update(int posr, int posc, long long value){
        update(root, 0, n - 1, posr, posc, value);
    }

    long long query(segtree *t, int l, int r, int qlr, int qrr, int qlc, int qrc){
        assert(t);
        if (l == qlr && r == qrr){
            return t->Query(qlc, qrc);
        }
        int mid = (r - l) / 2 + l;
        if (qrr <= mid){
            if (!t->ltree) return (long long) 0;
            //t->ltree = new segtree();
            return query(t->ltree, l, mid, qlr, qrr, qlc, qrc);
        }
        if (qlr > mid){
            if (!t->rtree) return (long long) 0;
            //t->rtree = new segtree();
            return query(t->rtree, mid + 1, r, qlr, qrr, qlc, qrc);
        }
        /*if (!t->ltree) t->ltree = new segtree();
        if (!t->rtree) t->rtree = new segtree();*/
        long long gcdl = (t->ltree)? query(t->ltree, l, mid, qlr, mid, qlc, qrc): (long long) 0;
        long long gcdr = (t->rtree)? query(t->rtree, mid + 1, r, mid + 1, qrr, qlc, qrc): (long long) 0;
        return gcd2(gcdl, gcdr);
    }

    long long Query(int qlr, int qrr, int qlc, int qrc){
        return query(root, 0, n - 1, qlr, qrr, qlc, qrc);
    }

};

segtree2d matrix;

void init(int R, int C) {
    //cerr << "init\n";
    n = R;
    m = C;
}

void update(int P, int Q, long long K) {
    //a[P][Q] = K;
    //cerr << "Update P Q K\n ";
    matrix.Update(P, Q, K);
    //cerr << "End Update P Q K\n";
}

long long calculate(int P, int Q, int U, int V) {
    /*long long gcd = 0;
    for (int i = P; i <= U; ++i)
        for (int j = Q; j <= V; ++j)
            gcd = gcd2(gcd, a[i][j]);*/
    //cerr << "Calculate P Q U V\n";
    long long gcd = matrix.Query(P, U, Q, V);
    //cerr << "End Calculate P Q U V\n";
    return gcd;
}

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