oj.uz

Submission #962986

# Submission time Handle Problem Language Result Execution time Memory
962986 2024-04-14T10:31:48 Z stev2005 Game (IOI13_game) C++17
63 / 100
 1186 ms 256000 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 356 ms 13528 KB Output is correct
5 Correct 261 ms 13980 KB Output is correct
6 Correct 293 ms 11460 KB Output is correct
7 Correct 326 ms 10036 KB Output is correct
8 Correct 213 ms 6080 KB Output is correct
9 Correct 319 ms 9216 KB Output is correct
10 Correct 263 ms 9568 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 568 ms 12476 KB Output is correct
13 Correct 988 ms 6604 KB Output is correct
14 Correct 206 ms 996 KB Output is correct
15 Correct 1143 ms 6076 KB Output is correct
16 Correct 167 ms 16980 KB Output is correct
17 Correct 463 ms 10428 KB Output is correct
18 Correct 689 ms 18896 KB Output is correct
19 Correct 673 ms 18808 KB Output is correct
20 Correct 602 ms 19096 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 368 ms 13016 KB Output is correct
13 Correct 238 ms 13076 KB Output is correct
14 Correct 305 ms 10916 KB Output is correct
15 Correct 309 ms 10768 KB Output is correct
16 Correct 241 ms 7388 KB Output is correct
17 Correct 330 ms 9652 KB Output is correct
18 Correct 310 ms 9820 KB Output is correct
19 Correct 582 ms 11640 KB Output is correct
20 Correct 1000 ms 6356 KB Output is correct
21 Correct 201 ms 1000 KB Output is correct
22 Correct 1186 ms 5000 KB Output is correct
23 Correct 154 ms 18092 KB Output is correct
24 Correct 451 ms 9904 KB Output is correct
25 Correct 759 ms 18224 KB Output is correct
26 Correct 594 ms 18428 KB Output is correct
27 Correct 555 ms 18880 KB Output is correct
28 Correct 459 ms 135852 KB Output is correct
29 Runtime error 1127 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 377 ms 14608 KB Output is correct
13 Correct 249 ms 13596 KB Output is correct
14 Correct 277 ms 9940 KB Output is correct
15 Correct 317 ms 10692 KB Output is correct
16 Correct 230 ms 6472 KB Output is correct
17 Correct 332 ms 10164 KB Output is correct
18 Correct 283 ms 10476 KB Output is correct
19 Correct 511 ms 12552 KB Output is correct
20 Correct 940 ms 5664 KB Output is correct
21 Correct 185 ms 852 KB Output is correct
22 Correct 1145 ms 5324 KB Output is correct
23 Correct 157 ms 17068 KB Output is correct
24 Correct 460 ms 10236 KB Output is correct
25 Correct 690 ms 18860 KB Output is correct
26 Correct 587 ms 18280 KB Output is correct
27 Correct 566 ms 18456 KB Output is correct
28 Correct 425 ms 136764 KB Output is correct
29 Runtime error 1099 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -