oj.uz

Submission #962732

# Submission time Handle Problem Language Result Execution time Memory
962732 2024-04-14T07:36:55 Z stev2005 Game (IOI13_game) C++17
63 / 100
 1325 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;
            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) t->l = new Node();
                return query(t->l, l, mid, ql, qr);
            }
            if (ql > mid){
                if (!t->r) t->r = new Node();
                return query(t->r, mid + 1, r, ql, qr);
            }
            if (!t->l) t->l = new Node();
            if (!t->r) t->r = new Node();
            return gcd2(query(t->l, l, mid, ql, mid),
                        query(t->r, mid + 1, r, mid + 1, qr));
        }

        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) t->ltree = new segtree();
            return query(t->ltree, l, mid, qlr, qrr, qlc, qrc);
        }
        if (qlr > mid){
            if (!t->rtree) 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 = query(t->ltree, l, mid, qlr, mid, qlc, qrc);
        long long gcdr = query(t->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(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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 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 604 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 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 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 387 ms 18208 KB Output is correct
5 Correct 273 ms 22612 KB Output is correct
6 Correct 347 ms 20228 KB Output is correct
7 Correct 392 ms 19980 KB Output is correct
8 Correct 244 ms 14404 KB Output is correct
9 Correct 387 ms 20304 KB Output is correct
10 Correct 342 ms 19796 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 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 647 ms 22584 KB Output is correct
13 Correct 1044 ms 8788 KB Output is correct
14 Correct 222 ms 5676 KB Output is correct
15 Correct 1285 ms 17620 KB Output is correct
16 Correct 171 ms 33620 KB Output is correct
17 Correct 618 ms 23168 KB Output is correct
18 Correct 1088 ms 35132 KB Output is correct
19 Correct 894 ms 35404 KB Output is correct
20 Correct 889 ms 34732 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 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 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 410 ms 18312 KB Output is correct
13 Correct 283 ms 22608 KB Output is correct
14 Correct 348 ms 20308 KB Output is correct
15 Correct 387 ms 20052 KB Output is correct
16 Correct 245 ms 14416 KB Output is correct
17 Correct 390 ms 20212 KB Output is correct
18 Correct 367 ms 19796 KB Output is correct
19 Correct 659 ms 26672 KB Output is correct
20 Correct 1094 ms 12628 KB Output is correct
21 Correct 209 ms 5828 KB Output is correct
22 Correct 1325 ms 17432 KB Output is correct
23 Correct 197 ms 33628 KB Output is correct
24 Correct 626 ms 23280 KB Output is correct
25 Correct 1088 ms 35216 KB Output is correct
26 Correct 932 ms 35344 KB Output is correct
27 Correct 871 ms 34988 KB Output is correct
28 Runtime error 502 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 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 604 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 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 427 ms 18228 KB Output is correct
13 Correct 294 ms 22648 KB Output is correct
14 Correct 365 ms 20208 KB Output is correct
15 Correct 374 ms 19924 KB Output is correct
16 Correct 243 ms 14412 KB Output is correct
17 Correct 352 ms 20304 KB Output is correct
18 Correct 335 ms 19792 KB Output is correct
19 Correct 645 ms 26612 KB Output is correct
20 Correct 1087 ms 12644 KB Output is correct
21 Correct 209 ms 5588 KB Output is correct
22 Correct 1294 ms 17424 KB Output is correct
23 Correct 192 ms 33728 KB Output is correct
24 Correct 577 ms 23244 KB Output is correct
25 Correct 1035 ms 35180 KB Output is correct
26 Correct 896 ms 35252 KB Output is correct
27 Correct 831 ms 34700 KB Output is correct
28 Runtime error 510 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -