oj.uz

Submission #687923

# Submission time Handle Problem Language Result Execution time Memory
687923 2023-01-27T04:43:51 Z vjudge1 Game (IOI13_game) C++17
100 / 100
 7295 ms 57228 KB 
#include <game.h>
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int oo = 2e9;

struct node {
    node *l, *r;
    int wt, val, g;
    ii co;
    node (ii pos, int x)
    {
        l = r = 0;
        wt = rand();
        val = g = x;
        co = pos;
    }
};
#define nd node*

inline int gg(nd x) {return x ? x->g : 0;}
inline void upd(nd x) {x->g = __gcd(__gcd(gg(x->l), gg(x->r)), x->val);}

inline void merg(nd &x, nd l, nd r)
{
    if (!l || !r) return void(x=l?l:r);
    if (l->wt < r->wt) merg(r->l, l, r->l), x = r;
    else merg(l->r, l->r, r), x = l;
    upd(x);
}

inline void split(nd x, nd &l, nd &r, ii pos)
{
    if (!x) return void(l=r=0);
    if (x->co <= pos) split(x->r, x->r, r, pos), l = x;
    else split(x->l, l, x->l, pos), r = x;
    upd(x);
}

inline void ins(nd &x, ii pos, int val)
{
    node *a, *b;
    split(x, x, a, {pos.ff, pos.ss-1});
    split(a, a, b, pos);
    merg(x, x, new node(pos, val));
//    merg(a, a, b);
    merg(x, x, b);
}

inline int qry1(nd &x, int l, int r)
{
    node *a, *b;
    split(x, x, a, {l-1, oo});
    split(a, a, b, {r, oo});
    int ans = gg(a);
    merg(a, a, b);
    merg(x, x, a);
    return ans;
}

struct Node {
    Node *l, *r;
    nd st;
    Node() {
        l = r = 0;
        st = 0;
    }
};
Node *root = new Node();

inline void upd(Node *&cur, int lx, int rx, int x, int y, int val)
{
    if (!cur) cur = new Node();
    ins(cur->st, {y, x}, val);
    if (lx == rx) return;
    int m = (lx + rx) >> 1;
    if (x <= m) upd(cur->l, lx, m, x, y, val);
    else upd(cur->r, m+1, rx, x, y, val);
}

inline int qry(Node *&x, int lb, int rb, int lx, int rx, int ly, int ry)
{
    if (lx > rx || !x) return 0;
    else if (lb == lx && rb == rx) return qry1(x->st, ly, ry);
    int m = (lb + rb) >> 1;
    return __gcd(qry(x->l, lb, m, lx, min(rx, m), ly, ry),
                 qry(x->r, m+1, rb, max(lx, m+1), rx, ly, ry));
}

int l1, r1;
void init(signed r, signed c) {
    l1 = 0, r1 = r - 1;
}

void update(signed x, signed y, int k) {
    upd(root, l1, r1, x, y, k);
}

int calculate(signed x, signed y, signed u, signed v) {
    return qry(root, l1, r1, x, u, y, v);
}

//signed main()
//{
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr); cout.tie(nullptr);
//    init(2, 3);
//    update(0, 0, 20);
//    update(0, 2, 15);
//    update(1, 1, 12);
//    cerr<<calculate(0, 0, 0, 2)<<"\n";
//    cerr<<calculate(0, 0, 1, 1)<<"\n";
//    update(0, 1, 6);
//    update(1, 1, 14);
//    cerr<<calculate(0, 0, 0, 2)<<"\n";
//    cerr<<calculate(0, 0, 1, 1)<<"\n";
//}

Subtask #1
10.0 / 10.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 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 0 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 0 ms 212 KB Output is correct
11 Correct 1 ms 212 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 793 ms 7008 KB Output is correct
5 Correct 343 ms 7372 KB Output is correct
6 Correct 1043 ms 4104 KB Output is correct
7 Correct 1195 ms 3772 KB Output is correct
8 Correct 783 ms 3272 KB Output is correct
9 Correct 1198 ms 3900 KB Output is correct
10 Correct 997 ms 3660 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1283 ms 11204 KB Output is correct
13 Correct 3510 ms 8048 KB Output is correct
14 Correct 552 ms 8268 KB Output is correct
15 Correct 3740 ms 8532 KB Output is correct
16 Correct 435 ms 8588 KB Output is correct
17 Correct 1720 ms 5204 KB Output is correct
18 Correct 3234 ms 8876 KB Output is correct
19 Correct 2489 ms 9016 KB Output is correct
20 Correct 2248 ms 8400 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 0 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 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 797 ms 6956 KB Output is correct
13 Correct 347 ms 7488 KB Output is correct
14 Correct 1039 ms 4232 KB Output is correct
15 Correct 1223 ms 3864 KB Output is correct
16 Correct 804 ms 3320 KB Output is correct
17 Correct 1150 ms 3904 KB Output is correct
18 Correct 995 ms 3748 KB Output is correct
19 Correct 1296 ms 11300 KB Output is correct
20 Correct 3529 ms 7868 KB Output is correct
21 Correct 554 ms 8416 KB Output is correct
22 Correct 3702 ms 8612 KB Output is correct
23 Correct 406 ms 8684 KB Output is correct
24 Correct 1659 ms 5252 KB Output is correct
25 Correct 2968 ms 8916 KB Output is correct
26 Correct 2445 ms 9048 KB Output is correct
27 Correct 2228 ms 8680 KB Output is correct
28 Correct 898 ms 25748 KB Output is correct
29 Correct 1699 ms 28804 KB Output is correct
30 Correct 4646 ms 23152 KB Output is correct
31 Correct 4240 ms 22692 KB Output is correct
32 Correct 811 ms 20100 KB Output is correct
33 Correct 1163 ms 20368 KB Output is correct
34 Correct 462 ms 25964 KB Output is correct
35 Correct 1880 ms 14116 KB Output is correct
36 Correct 3682 ms 26196 KB Output is correct
37 Correct 2875 ms 26596 KB Output is correct
38 Correct 2741 ms 25888 KB Output is correct
39 Correct 2459 ms 20548 KB Output is correct
40 Correct 0 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 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 212 KB Output is correct
12 Correct 816 ms 7016 KB Output is correct
13 Correct 347 ms 7424 KB Output is correct
14 Correct 1062 ms 4104 KB Output is correct
15 Correct 1196 ms 3796 KB Output is correct
16 Correct 795 ms 3232 KB Output is correct
17 Correct 1159 ms 3960 KB Output is correct
18 Correct 1002 ms 3608 KB Output is correct
19 Correct 1281 ms 11180 KB Output is correct
20 Correct 3523 ms 8028 KB Output is correct
21 Correct 561 ms 8376 KB Output is correct
22 Correct 3694 ms 8728 KB Output is correct
23 Correct 401 ms 8632 KB Output is correct
24 Correct 1693 ms 5388 KB Output is correct
25 Correct 2866 ms 8964 KB Output is correct
26 Correct 2453 ms 9092 KB Output is correct
27 Correct 2211 ms 8608 KB Output is correct
28 Correct 897 ms 25796 KB Output is correct
29 Correct 1673 ms 28924 KB Output is correct
30 Correct 4578 ms 23420 KB Output is correct
31 Correct 4183 ms 22680 KB Output is correct
32 Correct 804 ms 20284 KB Output is correct
33 Correct 1146 ms 20232 KB Output is correct
34 Correct 460 ms 25948 KB Output is correct
35 Correct 1891 ms 14012 KB Output is correct
36 Correct 3599 ms 26400 KB Output is correct
37 Correct 2816 ms 26404 KB Output is correct
38 Correct 2682 ms 25704 KB Output is correct
39 Correct 1238 ms 55044 KB Output is correct
40 Correct 2747 ms 57228 KB Output is correct
41 Correct 7295 ms 49580 KB Output is correct
42 Correct 6362 ms 48256 KB Output is correct
43 Correct 757 ms 55176 KB Output is correct
44 Correct 1350 ms 43492 KB Output is correct
45 Correct 2412 ms 20532 KB Output is correct
46 Correct 4863 ms 55412 KB Output is correct
47 Correct 4742 ms 55512 KB Output is correct
48 Correct 4285 ms 54960 KB Output is correct
49 Correct 0 ms 212 KB Output is correct