oj.uz

Submission #962969

# Submission time Handle Problem Language Result Execution time Memory
962969 2024-04-14T10:20:08 Z stev2005 Game (IOI13_game) C++17
63 / 100
 13000 ms 189632 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 segtree2d{
    struct segtree{
        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;

        //Node *root;
        //int root; it is always 0
        //segtree *ltree, *rtree;
        //long long key;
        int ltree, rtree;
        segtree(){
            ltree = -1;
            rtree = -1;
            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(0, 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(0, 0, m - 1, ql, qr);
        }

    };

    vector<segtree> t;

    //segtree *root;
    segtree2d(){
        //root = new segtree();
        t.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 = (t[i].ltree == -1)? (long long) 0: t[t[i].ltree].Query(posc, posc);
        long long rgcd = (t[i].rtree == -1)? (long long) 0: t[t[i].rtree].Query(posc, posc);
        long long value = gcd2(lgcd, rgcd);
        t[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";
            t[i].Update(posc, value);
            //cerr << "local update is done\n";
            return;
        }
        int mid = (r - l) / 2 + l;
        if (posr <= mid){
            if (t[i].ltree == -1){
                t[i].ltree = t.size();
                t.emplace_back();
            }
            update(t[i].ltree, l, mid, posr, posc, value);
        }
        else{
            if (t[i].rtree == -1){
                t[i].rtree = t.size();
                t.emplace_back();
            }
            update(t[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 t[i].Query(qlc, qrc);
        }
        int mid = (r - l) / 2 + l;
        if (qrr <= mid){
            if (t[i].ltree == -1) return (long long) 0;
            //t->ltree = new segtree();
            return query(t[i].ltree, l, mid, qlr, qrr, qlc, qrc);
        }
        if (qlr > mid){
            if (t[i].rtree == -1) return (long long) 0;
            //t->rtree = new segtree();
            return query(t[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 = (t[i].ltree == -1)? (long long) 0: query(t[i].ltree, l, mid, qlr, mid, qlc, qrc);
        long long gcdr = (t[i].rtree == -1)? (long long) 0: query(t[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 344 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 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 604 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1525 ms 13700 KB Output is correct
5 Correct 1382 ms 17556 KB Output is correct
6 Correct 1360 ms 15352 KB Output is correct
7 Correct 1538 ms 12100 KB Output is correct
8 Correct 564 ms 11800 KB Output is correct
9 Correct 1450 ms 12976 KB Output is correct
10 Correct 1452 ms 12068 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 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 0 ms 348 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 654 ms 13644 KB Output is correct
13 Correct 1049 ms 8620 KB Output is correct
14 Correct 218 ms 5180 KB Output is correct
15 Correct 1320 ms 12796 KB Output is correct
16 Correct 354 ms 15336 KB Output is correct
17 Correct 572 ms 12296 KB Output is correct
18 Correct 927 ms 16668 KB Output is correct
19 Correct 832 ms 16688 KB Output is correct
20 Correct 764 ms 16520 KB Output is correct
21 Correct 1 ms 348 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 1 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 1 ms 348 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 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1608 ms 13732 KB Output is correct
13 Correct 1391 ms 17416 KB Output is correct
14 Correct 1405 ms 15216 KB Output is correct
15 Correct 1402 ms 12024 KB Output is correct
16 Correct 534 ms 11584 KB Output is correct
17 Correct 1428 ms 13064 KB Output is correct
18 Correct 1400 ms 12144 KB Output is correct
19 Correct 614 ms 14908 KB Output is correct
20 Correct 1040 ms 8496 KB Output is correct
21 Correct 201 ms 5224 KB Output is correct
22 Correct 1255 ms 12712 KB Output is correct
23 Correct 295 ms 15384 KB Output is correct
24 Correct 572 ms 12332 KB Output is correct
25 Correct 848 ms 16692 KB Output is correct
26 Correct 787 ms 16964 KB Output is correct
27 Correct 752 ms 16736 KB Output is correct
28 Execution timed out 13092 ms 189632 KB Time limit exceeded
29 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 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 1 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 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 1450 ms 13984 KB Output is correct
13 Correct 1429 ms 17508 KB Output is correct
14 Correct 1389 ms 15148 KB Output is correct
15 Correct 1385 ms 11932 KB Output is correct
16 Correct 538 ms 11592 KB Output is correct
17 Correct 1401 ms 12956 KB Output is correct
18 Correct 1356 ms 12028 KB Output is correct
19 Correct 630 ms 15016 KB Output is correct
20 Correct 999 ms 8652 KB Output is correct
21 Correct 194 ms 5200 KB Output is correct
22 Correct 1254 ms 12724 KB Output is correct
23 Correct 302 ms 15240 KB Output is correct
24 Correct 541 ms 12476 KB Output is correct
25 Correct 793 ms 16704 KB Output is correct
26 Correct 835 ms 16684 KB Output is correct
27 Correct 691 ms 16600 KB Output is correct
28 Execution timed out 13008 ms 178952 KB Time limit exceeded
29 Halted 0 ms 0 KB -