Submission #962986

#	Time	Username	Problem	Language	Result	Execution time	Memory
962986		stev2005	Game (IOI13_game)	C++17	63 / 100	1186 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 Node{
            //Node *l, *r;
            int l, r;
            long long key;
            Node(){
                key = 0;
                l = -1;
                r = -1;
            }
            Node(long long _key){
                key = _key;
                l = -1;
                r = -1;
            }
        };
vector<Node> t;

struct segtree2d{
    
    struct segtree{
        
        int root;
        //int root; it is always 0
        //segtree *ltree, *rtree;
        //long long key;
        int ltree, rtree;
        segtree(){
            ltree = -1;
            rtree = -1;
            root = t.size();
            t.emplace_back();
            //key = 0;
        }

        inline void compute(int i){
            assert(i != -1);
            long long gcdl = (t[i].l == -1)? (long long) 0: t[t[i].l].key;
            long long gcdr = (t[i].r == -1)? (long long) 0: t[t[i].r].key;
            t[i].key = gcd2(gcdl, gcdr);
            /*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(int i, int l, int r, int pos, long long value){
            assert(i != -1);
            //cerr << "update: " << t << " " << l << " " << r << " " << pos << " " << value << "\n";
            if (l == r){
                t[i].key = value;
                return;
            }
            int mid = (r - l) / 2 + l;
            if (pos <= mid){
                if (t[i].l == -1){
                    t[i].l = t.size();
                    t.emplace_back();
                }
                update(t[i].l, l, mid, pos, value);
            }
            else{
                if (t[i].r == -1){
                    t[i].r = t.size();
                    t.emplace_back();
                }
                update(t[i].r, mid + 1, r, pos, value);
            }
            compute(i);
        }

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

        long long query(int i, int l, int r, int ql, int qr){
            assert(i != -1);
            if (t[i].key == 0) return (long long) 0;
            if (l == ql && r == qr) return t[i].key;
            int mid = (r - l) / 2 + l;
            if (qr <= mid){
                if (t[i].l == -1) return (long long) 0;
                //t->l = new Node();
                return query(t[i].l, l, mid, ql, qr);
            }
            if (ql > mid){
                if (t[i].r == -1) return (long long) 0;
                //t->r = new Node();
                return query(t[i].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[i].l == -1)? (long long) 0: query(t[i].l, l, mid, ql, mid);
            gcdr = (t[i].r == -1)? (long long) 0: query(t[i].r, mid + 1, r, mid + 1, qr);
            return gcd2(gcdl, gcdr);
        }

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

    };

    vector<segtree> tree;

    //segtree *root;
    segtree2d(){
        //root = new segtree();
        tree.emplace_back();
    }

    inline void compute(int i, int posc){
        assert(i != -1);
        /*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 = (tree[i].ltree == -1)? (long long) 0: tree[tree[i].ltree].Query(posc, posc);
        long long rgcd = (tree[i].rtree == -1)? (long long) 0: tree[tree[i].rtree].Query(posc, posc);
        long long value = gcd2(lgcd, rgcd);
        tree[i].Update(posc, value);
    }

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

    void Update(int posr, int posc, long long value){
        update(0, 0, n - 1, posr, posc, value);
        //t.shrink_to_fit();
    }

    long long query(int i, int l, int r, int qlr, int qrr, int qlc, int qrc){
        assert(i != -1);
        if (l == qlr && r == qrr){
            return tree[i].Query(qlc, qrc);
        }
        int mid = (r - l) / 2 + l;
        if (qrr <= mid){
            if (tree[i].ltree == -1) return (long long) 0;
            //t->ltree = new segtree();
            return query(tree[i].ltree, l, mid, qlr, qrr, qlc, qrc);
        }
        if (qlr > mid){
            if (tree[i].rtree == -1) return (long long) 0;
            //t->rtree = new segtree();
            return query(tree[i].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 = (tree[i].ltree == -1)? (long long) 0: query(tree[i].ltree, l, mid, qlr, mid, qlc, qrc);
        long long gcdr = (tree[i].rtree == -1)? (long long) 0: query(tree[i].rtree, mid + 1, r, mid + 1, qrr, qlc, qrc);
        return gcd2(gcdl, gcdr);
    }

    long long Query(int qlr, int qrr, int qlc, int qrc){
        return query(0, 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