oj.uz

Submission #591378

# Submission time Handle Problem Language Result Execution time Memory
591378 2022-07-07T10:55:35 Z SlavicG Game (IOI13_game) C++17
100 / 100
 6182 ms 67484 KB 
#include "game.h"
#include "bits/stdc++.h"
using namespace std;

using ll = long long;


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll a, ll b) {return a + rng() % (b - a + 1);}

int n, m;
struct node {
    node *left, *right;
    ll val;
};
ll gcd(ll a, ll b, ll c)  {
    return __gcd(__gcd(a, b), c);
}
struct Treap {
    struct node {
        node *l, *r;
        ll x, y;
        ll gc, val;
        node(ll X) {
            l = r = NULL;
            x = X, y = rand(1, (ll)1e9);
        }
    };
    node *root = 0;
    ll get(node *a) {
        if(a == NULL) return 0;
        return a->gc;
    }
    void split(node *t, node *&l, node *&r, int k) {
        if(!t) {
            l = r = NULL;
        } else if(t->x <= k) {
            split(t->r, t->r, r, k), l = t;
        } else {
            split(t->l, l, t->l, k), r = t;
        }
        if(t != NULL)
            t->gc = gcd(get(t->l), get(t->r), t->val);
    }
    void merge(node *&t, node *l, node *r) {
        if(!l) {
            t = r;
        } else if(!r) {
            t = l;
        } else if(l->y > r->y) {
            merge(l->r, l->r, r), t = l;
        } else {
            merge(r->l, l, r->l), t = r;
        }
        if(t != NULL)
            t->gc = gcd(get(t->l), get(t->r), t->val);
    }
    bool find(node* t, ll k) {
        if(t == NULL) return false;
        if(t->x == k) return true;
        if(t->x > k) return find(t->l, k);
        else return find(t->r, k);
    }
    ll query(int l, int r) {
        if(root == NULL) return 0;
        node *A, *B, *C;
        split(root, A, B, l - 1);
        split(B, B, C, r);
        ll ans = (B == NULL ? 0 : B->gc);
        merge(root, A, B);
        merge(root, root, C);
        return ans;
    }
    void modif(int j, ll val) {
        node *A, *B, *C;
        if(find(root, j)) {
            split(root, A, B, j - 1);
            split(B, B, C, j);
            B->val = val;
            merge(root, A, B);
            merge(root, root, C);
        } else {
            split(root, A, B, j - 1);
            C = new node(j);
            C->val = val;
            merge(root, A, C);
            merge(root, root, B);
        }
    }
};

struct purice {
    purice *left, *right;
    Treap paiu;
};

void modifi(purice *&i, int l, int r, int posi, int posj, ll val) {
    if(l > posi || r < posi) return;
    if(!i) i = new purice();
    if(l == posi && r == posi) {
        i->paiu.modif(posj, val);
        return;
    }
    int mid = (l + r) >> 1;

    modifi(i->left, l, mid, posi, posj, val);
    modifi(i->right, mid + 1, r, posi, posj, val);
    ll leftval = 0, rightval = 0;
    if(i->left) leftval = i->left->paiu.query(posj, posj);
    if(i->right) rightval = i->right->paiu.query(posj, posj);
    ll new_val = __gcd(leftval, rightval);

    i->paiu.modif(posj, new_val);
}

ll queryi(purice* i, int l, int r, int tli, int tri, int tlj, int trj) {
    if(l > tri || r < tli) return 0;
    if(!i || l > tri || r < tli) return 0;
    if(l >= tli && r <= tri) return i->paiu.query(tlj, trj);
    int mid = (l + r) >> 1;
    return __gcd(queryi(i->left, l, mid, tli, tri, tlj, trj), queryi(i->right, mid + 1, r, tli, tri, tlj, trj));
}

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;
}


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


void update(int P, int Q, long long K) {
    modifi(amogus, 0, n - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return queryi(amogus, 0, n - 1, 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 2 ms 308 KB Output is correct
3 Correct 2 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 2 ms 304 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 212 KB Output is correct
12 Correct 0 ms 300 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 885 ms 11352 KB Output is correct
5 Correct 461 ms 11228 KB Output is correct
6 Correct 1209 ms 8668 KB Output is correct
7 Correct 1363 ms 8548 KB Output is correct
8 Correct 887 ms 7564 KB Output is correct
9 Correct 1401 ms 8420 KB Output is correct
10 Correct 1212 ms 8108 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 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 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 308 KB Output is correct
12 Correct 1444 ms 13224 KB Output is correct
13 Correct 3177 ms 7540 KB Output is correct
14 Correct 473 ms 5588 KB Output is correct
15 Correct 3333 ms 8892 KB Output is correct
16 Correct 448 ms 11284 KB Output is correct
17 Correct 1902 ms 9776 KB Output is correct
18 Correct 3308 ms 12720 KB Output is correct
19 Correct 2816 ms 12852 KB Output is correct
20 Correct 2608 ms 12380 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 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 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 1 ms 212 KB Output is correct
8 Correct 1 ms 300 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 833 ms 11368 KB Output is correct
13 Correct 455 ms 11208 KB Output is correct
14 Correct 1218 ms 8624 KB Output is correct
15 Correct 1360 ms 8432 KB Output is correct
16 Correct 910 ms 7532 KB Output is correct
17 Correct 1299 ms 8504 KB Output is correct
18 Correct 1182 ms 8048 KB Output is correct
19 Correct 1300 ms 13296 KB Output is correct
20 Correct 2885 ms 7616 KB Output is correct
21 Correct 444 ms 5672 KB Output is correct
22 Correct 3108 ms 8988 KB Output is correct
23 Correct 497 ms 11280 KB Output is correct
24 Correct 1888 ms 9604 KB Output is correct
25 Correct 3392 ms 12764 KB Output is correct
26 Correct 3045 ms 12892 KB Output is correct
27 Correct 3034 ms 12432 KB Output is correct
28 Correct 1239 ms 36252 KB Output is correct
29 Correct 2128 ms 38852 KB Output is correct
30 Correct 4001 ms 28276 KB Output is correct
31 Correct 3577 ms 23352 KB Output is correct
32 Correct 636 ms 10132 KB Output is correct
33 Correct 943 ms 10476 KB Output is correct
34 Correct 672 ms 32728 KB Output is correct
35 Correct 2212 ms 23848 KB Output is correct
36 Correct 4094 ms 36756 KB Output is correct
37 Correct 3408 ms 37040 KB Output is correct
38 Correct 3383 ms 36400 KB Output is correct
39 Correct 2841 ms 30888 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 304 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 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 308 KB Output is correct
12 Correct 867 ms 11344 KB Output is correct
13 Correct 405 ms 11276 KB Output is correct
14 Correct 1260 ms 8660 KB Output is correct
15 Correct 1350 ms 8416 KB Output is correct
16 Correct 911 ms 7408 KB Output is correct
17 Correct 1323 ms 8496 KB Output is correct
18 Correct 1191 ms 8052 KB Output is correct
19 Correct 1316 ms 13312 KB Output is correct
20 Correct 3000 ms 7700 KB Output is correct
21 Correct 471 ms 5600 KB Output is correct
22 Correct 3235 ms 9164 KB Output is correct
23 Correct 475 ms 11332 KB Output is correct
24 Correct 1908 ms 9652 KB Output is correct
25 Correct 3415 ms 12720 KB Output is correct
26 Correct 2776 ms 13120 KB Output is correct
27 Correct 2617 ms 12308 KB Output is correct
28 Correct 1125 ms 36280 KB Output is correct
29 Correct 1938 ms 38940 KB Output is correct
30 Correct 4506 ms 28236 KB Output is correct
31 Correct 3872 ms 23304 KB Output is correct
32 Correct 690 ms 10152 KB Output is correct
33 Correct 969 ms 10500 KB Output is correct
34 Correct 663 ms 32664 KB Output is correct
35 Correct 2206 ms 23732 KB Output is correct
36 Correct 4107 ms 36816 KB Output is correct
37 Correct 3322 ms 37120 KB Output is correct
38 Correct 3338 ms 36500 KB Output is correct
39 Correct 1534 ms 65448 KB Output is correct
40 Correct 3380 ms 67484 KB Output is correct
41 Correct 6182 ms 52096 KB Output is correct
42 Correct 5429 ms 41132 KB Output is correct
43 Correct 1268 ms 62280 KB Output is correct
44 Correct 1012 ms 10748 KB Output is correct
45 Correct 2865 ms 30812 KB Output is correct
46 Correct 5362 ms 66532 KB Output is correct
47 Correct 5464 ms 66368 KB Output is correct
48 Correct 5118 ms 65996 KB Output is correct
49 Correct 1 ms 212 KB Output is correct