oj.uz

Submission #52026

# Submission time Handle Problem Language Result Execution time Memory
52026 2018-06-23T09:54:40 Z Crown Game (IOI13_game) C++14
80 / 100
 13000 ms 183024 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;

int 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 treap_node
{
    ll val, gcd;
    int key, key2, prio;
    treap_node *left, *right;
    treap_node(int _key, int _key2, ll _val)
    {
        val = gcd = _val;
        key = _key; key2 = _key2;
        prio = (rand()<<16)^rand();
        left = right = NULL;
    }
    void calc()
    {
        gcd = val;
        if(left) gcd = gcd2(gcd, left->gcd);
        if(right) gcd = gcd2(gcd, right->gcd);
    }
};

treap_node* merge(treap_node *L, treap_node *R)
{
    if(!L || !R) return L?L:R;
    if(L->prio > R->prio)
    {
        L->right = merge(L->right, R);
        L->calc();
        return L;
    }
    else
    {
        R->left = merge(L, R->left);
        R->calc();
        return R;
    }
} 
void split(treap_node *big, treap_node* &L, treap_node* &R, int key, int key2)
{
    L = R = NULL;
    if(!big)
    {
        return;
    }
    if(big->key< key || (big->key == key && big->key2<= key2))
    {
        L = big;
        split(big->right, big->right, R, key, key2);
    }
    else 
    {
        R = big;
        split(big->left, L, big->left, key, key2);
    }
    big->calc();
}

struct node
{
    treap_node *x;
    node *left, *right;
    node()
    {
        x = NULL;
        left = right = NULL;
    }
    node* getL()
    {
        if(left) return left;
        return left = new node();
    }
    node* getR()
    {
        if(right) return right;
        return right = new node();
    }
};

ll ask(node *u, int i1, int j1, int i2, int j2, int L = 0, int R = maxn-1)
{
    if(!u) return 0;
    if(i1> R || i2< L) return 0;
    if(i1<= L && R<= i2)
    {
        treap_node *one, *two;
        one = two = NULL;
        split(u->x, one, u->x, j1-1, 1e9+5);
        split(u->x, u->x, two, j2, 1e9+5);
        ll ret = u->x?u->x->gcd:0;
        u->x = merge(one, u->x);
        u->x = merge(u->x, two);
        return ret;
    }
    ll x = ask(u->left, i1, j1, i2, j2, L, (L+R)/2);
    ll y = ask(u->right, i1, j1, i2, j2, (L+R)/2+1, R);
    return gcd2(x, y);
}

void Update(node *u, int x, int y, ll val, int L = 0, int R = maxn-1)
{
    treap_node *one, *two;
    one = two = NULL;
    split(u->x, one, u->x, y, x-1);
    split(u->x, u->x, two, y, x);
    if(!(u->x))
    {
        u->x = new treap_node(y, x, val);
    }
    else
    {
        assert(!(u->x->left));
        assert(!(u->x->right));
        u->x->val = u->x->gcd = val;
    }
    u->x = merge(one, u->x);
    u->x = merge(u->x, two);
    if(L == R) return; 
    int M = (L+R)/2;
    if(x<= M) Update(u->getL(), x, y, val, L, M);
    else Update(u->getR(), x, y, val, M+1, R);
}

node *root;

void init(int R, int C)
{
    srand(time(NULL));
    maxn = R;
    root = new node();
}

void update(int P, int Q, long long K)
{
    Update(root, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    return ask(root, P, Q, U, V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 496 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 2 ms 568 KB Output is correct
9 Correct 3 ms 652 KB Output is correct
10 Correct 3 ms 656 KB Output is correct
11 Correct 3 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 676 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 1432 ms 11708 KB Output is correct
5 Correct 560 ms 16072 KB Output is correct
6 Correct 3063 ms 17632 KB Output is correct
7 Correct 3195 ms 22168 KB Output is correct
8 Correct 2128 ms 25712 KB Output is correct
9 Correct 3291 ms 31072 KB Output is correct
10 Correct 2685 ms 35284 KB Output is correct
11 Correct 2 ms 35284 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35284 KB Output is correct
2 Correct 4 ms 35284 KB Output is correct
3 Correct 4 ms 35284 KB Output is correct
4 Correct 2 ms 35284 KB Output is correct
5 Correct 2 ms 35284 KB Output is correct
6 Correct 4 ms 35284 KB Output is correct
7 Correct 2 ms 35284 KB Output is correct
8 Correct 2 ms 35284 KB Output is correct
9 Correct 3 ms 35284 KB Output is correct
10 Correct 3 ms 35284 KB Output is correct
11 Correct 3 ms 35284 KB Output is correct
12 Correct 1960 ms 47000 KB Output is correct
13 Correct 8170 ms 47000 KB Output is correct
14 Correct 1359 ms 47000 KB Output is correct
15 Correct 8962 ms 55508 KB Output is correct
16 Correct 1061 ms 61588 KB Output is correct
17 Correct 5046 ms 63112 KB Output is correct
18 Correct 9344 ms 72220 KB Output is correct
19 Correct 7540 ms 77468 KB Output is correct
20 Correct 8060 ms 82244 KB Output is correct
21 Correct 2 ms 82244 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 82244 KB Output is correct
2 Correct 4 ms 82244 KB Output is correct
3 Correct 3 ms 82244 KB Output is correct
4 Correct 3 ms 82244 KB Output is correct
5 Correct 2 ms 82244 KB Output is correct
6 Correct 3 ms 82244 KB Output is correct
7 Correct 2 ms 82244 KB Output is correct
8 Correct 2 ms 82244 KB Output is correct
9 Correct 4 ms 82244 KB Output is correct
10 Correct 3 ms 82244 KB Output is correct
11 Correct 3 ms 82244 KB Output is correct
12 Correct 1626 ms 85140 KB Output is correct
13 Correct 529 ms 89440 KB Output is correct
14 Correct 3055 ms 91036 KB Output is correct
15 Correct 3462 ms 95296 KB Output is correct
16 Correct 2300 ms 98944 KB Output is correct
17 Correct 3205 ms 104216 KB Output is correct
18 Correct 3022 ms 108652 KB Output is correct
19 Correct 2235 ms 120152 KB Output is correct
20 Correct 8068 ms 120152 KB Output is correct
21 Correct 1402 ms 120152 KB Output is correct
22 Correct 9374 ms 128764 KB Output is correct
23 Correct 963 ms 134668 KB Output is correct
24 Correct 4795 ms 134668 KB Output is correct
25 Correct 9204 ms 134996 KB Output is correct
26 Correct 7826 ms 135040 KB Output is correct
27 Correct 8045 ms 135040 KB Output is correct
28 Correct 2264 ms 151868 KB Output is correct
29 Correct 2878 ms 154664 KB Output is correct
30 Correct 10748 ms 154664 KB Output is correct
31 Correct 9300 ms 154664 KB Output is correct
32 Correct 1922 ms 154664 KB Output is correct
33 Correct 2894 ms 154664 KB Output is correct
34 Correct 905 ms 154664 KB Output is correct
35 Correct 5323 ms 154664 KB Output is correct
36 Correct 9868 ms 154664 KB Output is correct
37 Correct 8176 ms 154664 KB Output is correct
38 Correct 9019 ms 154664 KB Output is correct
39 Correct 6825 ms 154664 KB Output is correct
40 Correct 2 ms 154664 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 154664 KB Output is correct
2 Correct 4 ms 154664 KB Output is correct
3 Correct 3 ms 154664 KB Output is correct
4 Correct 2 ms 154664 KB Output is correct
5 Correct 2 ms 154664 KB Output is correct
6 Correct 3 ms 154664 KB Output is correct
7 Correct 2 ms 154664 KB Output is correct
8 Correct 3 ms 154664 KB Output is correct
9 Correct 4 ms 154664 KB Output is correct
10 Correct 3 ms 154664 KB Output is correct
11 Correct 3 ms 154664 KB Output is correct
12 Correct 1296 ms 154664 KB Output is correct
13 Correct 538 ms 154664 KB Output is correct
14 Correct 2889 ms 154664 KB Output is correct
15 Correct 3196 ms 154664 KB Output is correct
16 Correct 2053 ms 154664 KB Output is correct
17 Correct 3156 ms 154664 KB Output is correct
18 Correct 2808 ms 154664 KB Output is correct
19 Correct 2264 ms 154664 KB Output is correct
20 Correct 8131 ms 154664 KB Output is correct
21 Correct 1290 ms 154664 KB Output is correct
22 Correct 9106 ms 154664 KB Output is correct
23 Correct 838 ms 154664 KB Output is correct
24 Correct 4854 ms 154664 KB Output is correct
25 Correct 9295 ms 154664 KB Output is correct
26 Correct 7218 ms 154664 KB Output is correct
27 Correct 8527 ms 154664 KB Output is correct
28 Correct 2361 ms 154664 KB Output is correct
29 Correct 2863 ms 154676 KB Output is correct
30 Correct 10368 ms 154676 KB Output is correct
31 Correct 9335 ms 154676 KB Output is correct
32 Correct 1895 ms 154676 KB Output is correct
33 Correct 3021 ms 154676 KB Output is correct
34 Correct 902 ms 154676 KB Output is correct
35 Correct 5565 ms 154676 KB Output is correct
36 Correct 10730 ms 154676 KB Output is correct
37 Correct 8096 ms 154676 KB Output is correct
38 Correct 8942 ms 154676 KB Output is correct
39 Correct 3012 ms 180992 KB Output is correct
40 Correct 4682 ms 183024 KB Output is correct
41 Execution timed out 13045 ms 183024 KB Time limit exceeded
42 Halted 0 ms 0 KB -