oj.uz

Submission #962748

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

        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) return (long long) 0;
            //t->ltree = new segtree();
            return query(t->ltree, l, mid, qlr, qrr, qlc, qrc);
        }
        if (qlr > mid){
            if (!t->rtree) return (long long) 0;
            //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 = (t->ltree)? query(t->ltree, l, mid, qlr, mid, qlc, qrc): (long long) 0;
        long long gcdr = (t->rtree)? query(t->rtree, mid + 1, r, mid + 1, qrr, qlc, qrc): (long long) 0;
        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 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 768 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 444 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 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 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 344 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 408 ms 20936 KB Output is correct
5 Correct 311 ms 21172 KB Output is correct
6 Correct 365 ms 18560 KB Output is correct
7 Correct 405 ms 18124 KB Output is correct
8 Correct 258 ms 12372 KB Output is correct
9 Correct 366 ms 18160 KB Output is correct
10 Correct 317 ms 17648 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 1 ms 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 700 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 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 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 612 ms 24980 KB Output is correct
13 Correct 969 ms 11024 KB Output is correct
14 Correct 207 ms 3672 KB Output is correct
15 Correct 1196 ms 15556 KB Output is correct
16 Correct 183 ms 31796 KB Output is correct
17 Correct 573 ms 20840 KB Output is correct
18 Correct 1026 ms 32816 KB Output is correct
19 Correct 853 ms 32688 KB Output is correct
20 Correct 797 ms 32256 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 348 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 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 0 ms 352 KB Output is correct
9 Correct 1 ms 444 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 375 ms 20848 KB Output is correct
13 Correct 296 ms 20860 KB Output is correct
14 Correct 322 ms 18200 KB Output is correct
15 Correct 383 ms 17960 KB Output is correct
16 Correct 245 ms 12504 KB Output is correct
17 Correct 355 ms 18056 KB Output is correct
18 Correct 360 ms 17744 KB Output is correct
19 Correct 584 ms 24696 KB Output is correct
20 Correct 928 ms 10872 KB Output is correct
21 Correct 195 ms 3700 KB Output is correct
22 Correct 1140 ms 15772 KB Output is correct
23 Correct 167 ms 31872 KB Output is correct
24 Correct 565 ms 20972 KB Output is correct
25 Correct 1018 ms 32972 KB Output is correct
26 Correct 826 ms 32852 KB Output is correct
27 Correct 824 ms 32004 KB Output is correct
28 Runtime error 411 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 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 360 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 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 444 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 376 ms 20868 KB Output is correct
13 Correct 275 ms 21104 KB Output is correct
14 Correct 337 ms 18168 KB Output is correct
15 Correct 382 ms 17900 KB Output is correct
16 Correct 235 ms 12472 KB Output is correct
17 Correct 365 ms 18192 KB Output is correct
18 Correct 360 ms 17696 KB Output is correct
19 Correct 577 ms 24756 KB Output is correct
20 Correct 928 ms 10988 KB Output is correct
21 Correct 199 ms 3684 KB Output is correct
22 Correct 1151 ms 15604 KB Output is correct
23 Correct 185 ms 31824 KB Output is correct
24 Correct 537 ms 20856 KB Output is correct
25 Correct 988 ms 32692 KB Output is correct
26 Correct 824 ms 32932 KB Output is correct
27 Correct 774 ms 32248 KB Output is correct
28 Runtime error 402 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -