oj.uz

Submission #825803

# Submission time Handle Problem Language Result Execution time Memory
825803 2023-08-15T08:16:02 Z 79brue Game (IOI13_game) C++17
100 / 100
 3210 ms 175452 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;

struct segTree1d{
    struct Node{
        Node *lc, *rc;
        ll val; int loc; /// loc: 걸어둔 정점이면 그 위치, 아니면 0

        Node(){
            lc = rc = nullptr;
            val = 0, loc = -1;
        }

        ~Node(){
            if(lc) delete lc;
            if(rc) delete rc;
        }

        void update(int l, int r, int x, ll v){
            if(loc != -1){
                int m = (l+r)>>1;
                if(loc <= m) lc = new Node(), lc->update(l, m, loc, val);
                else rc = new Node(), rc->update(m+1, r, loc, val);
                loc = -1;
                val = __gcd(lc?lc->val:0, rc?rc->val:0);
            }
            if(l==r){
                val = v;
                return;
            }
            if(!val && !lc && !rc){
                val = v, loc = x;
                return;
            }
            int m = (l+r)>>1;
            if(x<=m){
                if(!lc) lc = new Node();
                lc->update(l, m, x, v);
            }
            else{
                if(!rc) rc = new Node();
                rc->update(m+1, r, x, v);
            }
            val = __gcd(lc?lc->val:0, rc?rc->val:0);
        }

        ll query(int l, int r, int s, int e){
            if(loc != -1){
                if(loc < s || e < loc) return 0;
                else return val;
            }
            if(r<s || e<l) return 0;
            if(s<=l && r<=e) return val;
            int m = (l+r)>>1;
            return __gcd(lc ? lc->query(l, m, s, e) : 0, rc ? rc->query(m+1, r, s, e) : 0);
        }
    } *root;

    segTree1d(){
        root = new Node();
    }

    void update(int y, ll v){
        root->update(0, m-1, y, v);
    }

    ll query(int yl, int yr){
        return root->query(0, m-1, yl, yr);
    }
};

struct segTree2d{
    struct Node{
        Node *lc, *rc;
        segTree1d tree;

        Node(){
            lc = rc = nullptr;
            tree = segTree1d();
        }

        ~Node(){
            if(lc) delete lc;
            if(rc) delete rc;
        }

        void update(int l, int r, int x, int y, ll v){
            if(l==r){
                tree.update(y, v);
                return;
            }
            int m = (l+r)>>1;
            if(x<=m){
                if(!lc) lc = new Node();
                lc->update(l, m, x, y, v);
                tree.update(y, __gcd(lc->tree.query(y, y), rc ? rc->tree.query(y, y) : 0));
            }
            else{
                if(!rc) rc = new Node();
                rc->update(m+1, r, x, y, v);
                tree.update(y, __gcd(rc->tree.query(y, y), lc ? lc->tree.query(y, y) : 0));
            }
        }

        ll query(int l, int r, int s, int e, int ys, int ye){
            if(r<s || e<l) return 0;
            if(s<=l && r<=e) return tree.query(ys, ye);
            int m = (l+r)>>1;
            return __gcd(lc ? lc->query(l, m, s, e, ys, ye) : 0, rc ? rc->query(m+1, r, s, e, ys, ye) : 0);
        }
    } *root;

    segTree2d(){
        root = new Node();
    }

    void update(int x, int y, ll v){
        root->update(0, n-1, x, y, v);
    }

    ll query(int xs, int xe, int ys, int ye){
        return root->query(0, n-1, xs, xe, ys, ye);
    }
} tree;

void init(int R, int C){
    n = R, m = C;
}

void update(int P, int Q, ll K) {
    tree.update(P, Q, K);
}

ll calculate(int P, int Q, int U, int V){
    return tree.query(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 370 ms 13540 KB Output is correct
5 Correct 251 ms 13388 KB Output is correct
6 Correct 306 ms 10928 KB Output is correct
7 Correct 438 ms 10676 KB Output is correct
8 Correct 248 ms 8428 KB Output is correct
9 Correct 326 ms 10660 KB Output is correct
10 Correct 403 ms 10380 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 653 ms 16904 KB Output is correct
13 Correct 1117 ms 10644 KB Output is correct
14 Correct 202 ms 5716 KB Output is correct
15 Correct 1189 ms 13552 KB Output is correct
16 Correct 150 ms 15916 KB Output is correct
17 Correct 512 ms 12076 KB Output is correct
18 Correct 830 ms 17344 KB Output is correct
19 Correct 718 ms 17584 KB Output is correct
20 Correct 681 ms 16960 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 300 KB Output is correct
12 Correct 370 ms 13596 KB Output is correct
13 Correct 253 ms 13420 KB Output is correct
14 Correct 381 ms 10964 KB Output is correct
15 Correct 338 ms 10612 KB Output is correct
16 Correct 290 ms 8532 KB Output is correct
17 Correct 431 ms 10648 KB Output is correct
18 Correct 397 ms 10392 KB Output is correct
19 Correct 610 ms 17024 KB Output is correct
20 Correct 1187 ms 10644 KB Output is correct
21 Correct 224 ms 5708 KB Output is correct
22 Correct 1256 ms 13540 KB Output is correct
23 Correct 160 ms 15960 KB Output is correct
24 Correct 515 ms 12096 KB Output is correct
25 Correct 854 ms 17352 KB Output is correct
26 Correct 829 ms 17556 KB Output is correct
27 Correct 692 ms 16924 KB Output is correct
28 Correct 392 ms 56556 KB Output is correct
29 Correct 948 ms 51688 KB Output is correct
30 Correct 2526 ms 48340 KB Output is correct
31 Correct 2374 ms 88408 KB Output is correct
32 Correct 355 ms 10648 KB Output is correct
33 Correct 482 ms 14636 KB Output is correct
34 Correct 203 ms 45420 KB Output is correct
35 Correct 668 ms 30032 KB Output is correct
36 Correct 1262 ms 49460 KB Output is correct
37 Correct 1054 ms 49816 KB Output is correct
38 Correct 963 ms 49132 KB Output is correct
39 Correct 828 ms 40444 KB Output is correct
40 Correct 0 ms 296 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 272 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 367 ms 13624 KB Output is correct
13 Correct 251 ms 13396 KB Output is correct
14 Correct 314 ms 11000 KB Output is correct
15 Correct 358 ms 10676 KB Output is correct
16 Correct 234 ms 8516 KB Output is correct
17 Correct 330 ms 10732 KB Output is correct
18 Correct 299 ms 10344 KB Output is correct
19 Correct 586 ms 16916 KB Output is correct
20 Correct 1022 ms 10640 KB Output is correct
21 Correct 199 ms 5600 KB Output is correct
22 Correct 1198 ms 13476 KB Output is correct
23 Correct 143 ms 15968 KB Output is correct
24 Correct 514 ms 12100 KB Output is correct
25 Correct 882 ms 17424 KB Output is correct
26 Correct 707 ms 17500 KB Output is correct
27 Correct 684 ms 16960 KB Output is correct
28 Correct 346 ms 56604 KB Output is correct
29 Correct 1002 ms 51704 KB Output is correct
30 Correct 2565 ms 48296 KB Output is correct
31 Correct 2384 ms 88452 KB Output is correct
32 Correct 353 ms 10620 KB Output is correct
33 Correct 485 ms 14524 KB Output is correct
34 Correct 196 ms 45404 KB Output is correct
35 Correct 634 ms 30048 KB Output is correct
36 Correct 1211 ms 49648 KB Output is correct
37 Correct 1008 ms 49752 KB Output is correct
38 Correct 951 ms 49192 KB Output is correct
39 Correct 501 ms 112356 KB Output is correct
40 Correct 1471 ms 96100 KB Output is correct
41 Correct 3205 ms 96348 KB Output is correct
42 Correct 3210 ms 175452 KB Output is correct
43 Correct 352 ms 90868 KB Output is correct
44 Correct 522 ms 11024 KB Output is correct
45 Correct 783 ms 40492 KB Output is correct
46 Correct 1720 ms 94972 KB Output is correct
47 Correct 1706 ms 95016 KB Output is correct
48 Correct 1659 ms 94432 KB Output is correct
49 Correct 0 ms 212 KB Output is correct