oj.uz

Submission #962854

# Submission time Handle Problem Language Result Execution time Memory
962854 2024-04-14T09:03:35 Z stev2005 Game (IOI13_game) C++17
63 / 100
 1211 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){
            long long gcdl = (t->l)? t->l->key: (long long)0;
            long long gcdr = (t->r)? t->r->key: (long long)0;
            t->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(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)? t->ltree->Query(posc, posc): (long long) 0;
        long long rgcd = (t->rtree)? t->rtree->Query(posc, posc): (long long) 0;
        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 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 1 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 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 342 ms 12628 KB Output is correct
5 Correct 247 ms 13132 KB Output is correct
6 Correct 321 ms 9960 KB Output is correct
7 Correct 317 ms 9552 KB Output is correct
8 Correct 219 ms 6748 KB Output is correct
9 Correct 331 ms 9768 KB Output is correct
10 Correct 306 ms 9256 KB Output is correct
11 Correct 0 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 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 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 424 KB Output is correct
12 Correct 565 ms 15768 KB Output is correct
13 Correct 901 ms 6196 KB Output is correct
14 Correct 183 ms 940 KB Output is correct
15 Correct 1079 ms 8916 KB Output is correct
16 Correct 157 ms 18264 KB Output is correct
17 Correct 485 ms 11372 KB Output is correct
18 Correct 920 ms 18776 KB Output is correct
19 Correct 689 ms 18704 KB Output is correct
20 Correct 654 ms 18136 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 344 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 0 ms 344 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 348 KB Output is correct
12 Correct 348 ms 12572 KB Output is correct
13 Correct 257 ms 12976 KB Output is correct
14 Correct 333 ms 9908 KB Output is correct
15 Correct 320 ms 9552 KB Output is correct
16 Correct 233 ms 6564 KB Output is correct
17 Correct 352 ms 9908 KB Output is correct
18 Correct 282 ms 9364 KB Output is correct
19 Correct 540 ms 16072 KB Output is correct
20 Correct 974 ms 6236 KB Output is correct
21 Correct 179 ms 1028 KB Output is correct
22 Correct 1083 ms 8972 KB Output is correct
23 Correct 162 ms 18176 KB Output is correct
24 Correct 465 ms 11572 KB Output is correct
25 Correct 810 ms 18608 KB Output is correct
26 Correct 741 ms 18668 KB Output is correct
27 Correct 676 ms 18180 KB Output is correct
28 Correct 686 ms 251960 KB Output is correct
29 Runtime error 1211 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 1 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 1 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 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 351 ms 12664 KB Output is correct
13 Correct 266 ms 12880 KB Output is correct
14 Correct 320 ms 10044 KB Output is correct
15 Correct 353 ms 10128 KB Output is correct
16 Correct 251 ms 6800 KB Output is correct
17 Correct 321 ms 9612 KB Output is correct
18 Correct 287 ms 9308 KB Output is correct
19 Correct 491 ms 15852 KB Output is correct
20 Correct 934 ms 6480 KB Output is correct
21 Correct 183 ms 864 KB Output is correct
22 Correct 1110 ms 8824 KB Output is correct
23 Correct 174 ms 18476 KB Output is correct
24 Correct 470 ms 11424 KB Output is correct
25 Correct 882 ms 18712 KB Output is correct
26 Correct 719 ms 18696 KB Output is correct
27 Correct 698 ms 18300 KB Output is correct
28 Correct 713 ms 251676 KB Output is correct
29 Runtime error 1184 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -