oj.uz

Submission #962907

# Submission time Handle Problem Language Result Execution time Memory
962907 2024-04-14T09:36:44 Z stev2005 Game (IOI13_game) C++17
80 / 100
 2806 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 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);
        }

        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);
    }

    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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 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 600 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 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 361 ms 10296 KB Output is correct
5 Correct 268 ms 10428 KB Output is correct
6 Correct 298 ms 7012 KB Output is correct
7 Correct 323 ms 6628 KB Output is correct
8 Correct 223 ms 5320 KB Output is correct
9 Correct 317 ms 7036 KB Output is correct
10 Correct 278 ms 6316 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.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 348 KB Output is correct
10 Correct 1 ms 500 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 569 ms 12888 KB Output is correct
13 Correct 952 ms 4792 KB Output is correct
14 Correct 226 ms 1168 KB Output is correct
15 Correct 1237 ms 6308 KB Output is correct
16 Correct 155 ms 13652 KB Output is correct
17 Correct 517 ms 8768 KB Output is correct
18 Correct 704 ms 14024 KB Output is correct
19 Correct 638 ms 14168 KB Output is correct
20 Correct 573 ms 13704 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
17.0 / 17.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 1 ms 348 KB Output is correct
6 Correct 1 ms 344 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 348 KB Output is correct
11 Correct 1 ms 500 KB Output is correct
12 Correct 374 ms 9836 KB Output is correct
13 Correct 280 ms 10556 KB Output is correct
14 Correct 291 ms 6892 KB Output is correct
15 Correct 323 ms 6932 KB Output is correct
16 Correct 215 ms 5320 KB Output is correct
17 Correct 319 ms 7364 KB Output is correct
18 Correct 266 ms 6164 KB Output is correct
19 Correct 565 ms 12824 KB Output is correct
20 Correct 960 ms 4764 KB Output is correct
21 Correct 198 ms 1108 KB Output is correct
22 Correct 1109 ms 6420 KB Output is correct
23 Correct 168 ms 13648 KB Output is correct
24 Correct 446 ms 8952 KB Output is correct
25 Correct 724 ms 14216 KB Output is correct
26 Correct 595 ms 14164 KB Output is correct
27 Correct 637 ms 13508 KB Output is correct
28 Correct 530 ms 145804 KB Output is correct
29 Correct 1133 ms 163780 KB Output is correct
30 Correct 2806 ms 116652 KB Output is correct
31 Correct 2727 ms 95960 KB Output is correct
32 Correct 308 ms 1264 KB Output is correct
33 Correct 445 ms 3672 KB Output is correct
34 Correct 432 ms 161036 KB Output is correct
35 Correct 734 ms 81252 KB Output is correct
36 Correct 1477 ms 160568 KB Output is correct
37 Correct 1215 ms 158768 KB Output is correct
38 Correct 1218 ms 159836 KB Output is correct
39 Correct 999 ms 126232 KB Output is correct
40 Correct 0 ms 344 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 600 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 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 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 362 ms 9964 KB Output is correct
13 Correct 254 ms 10304 KB Output is correct
14 Correct 291 ms 7208 KB Output is correct
15 Correct 323 ms 6724 KB Output is correct
16 Correct 221 ms 5156 KB Output is correct
17 Correct 296 ms 7036 KB Output is correct
18 Correct 273 ms 6112 KB Output is correct
19 Correct 538 ms 12864 KB Output is correct
20 Correct 996 ms 4788 KB Output is correct
21 Correct 209 ms 848 KB Output is correct
22 Correct 1195 ms 6476 KB Output is correct
23 Correct 159 ms 13820 KB Output is correct
24 Correct 496 ms 8884 KB Output is correct
25 Correct 774 ms 14260 KB Output is correct
26 Correct 642 ms 14192 KB Output is correct
27 Correct 582 ms 13868 KB Output is correct
28 Correct 525 ms 148308 KB Output is correct
29 Correct 1089 ms 162488 KB Output is correct
30 Correct 2792 ms 116644 KB Output is correct
31 Correct 2698 ms 94676 KB Output is correct
32 Correct 325 ms 1260 KB Output is correct
33 Correct 427 ms 3668 KB Output is correct
34 Correct 409 ms 159644 KB Output is correct
35 Correct 752 ms 81704 KB Output is correct
36 Correct 1406 ms 159984 KB Output is correct
37 Correct 1213 ms 161208 KB Output is correct
38 Correct 1167 ms 160520 KB Output is correct
39 Runtime error 627 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -