oj.uz

Submission #52024

# Submission time Handle Problem Language Result Execution time Memory
52024 2018-06-23T09:47:37 Z Crown Game (IOI13_game) C++14
80 / 100
 13000 ms 387072 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 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 600 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 612 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Correct 1344 ms 11848 KB Output is correct
5 Correct 502 ms 16044 KB Output is correct
6 Correct 2745 ms 17740 KB Output is correct
7 Correct 3221 ms 22020 KB Output is correct
8 Correct 2063 ms 25660 KB Output is correct
9 Correct 2958 ms 31044 KB Output is correct
10 Correct 2681 ms 35436 KB Output is correct
11 Correct 2 ms 35436 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 35436 KB Output is correct
2 Correct 3 ms 35436 KB Output is correct
3 Correct 3 ms 35436 KB Output is correct
4 Correct 2 ms 35436 KB Output is correct
5 Correct 2 ms 35436 KB Output is correct
6 Correct 3 ms 35436 KB Output is correct
7 Correct 2 ms 35436 KB Output is correct
8 Correct 3 ms 35436 KB Output is correct
9 Correct 3 ms 35436 KB Output is correct
10 Correct 3 ms 35436 KB Output is correct
11 Correct 3 ms 35436 KB Output is correct
12 Correct 1890 ms 47192 KB Output is correct
13 Correct 8138 ms 47192 KB Output is correct
14 Correct 1317 ms 47192 KB Output is correct
15 Correct 8929 ms 55540 KB Output is correct
16 Correct 1051 ms 61916 KB Output is correct
17 Correct 4704 ms 63420 KB Output is correct
18 Correct 8818 ms 72324 KB Output is correct
19 Correct 7446 ms 77924 KB Output is correct
20 Correct 7868 ms 82652 KB Output is correct
21 Correct 3 ms 82652 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 82652 KB Output is correct
2 Correct 5 ms 82652 KB Output is correct
3 Correct 4 ms 82652 KB Output is correct
4 Correct 2 ms 82652 KB Output is correct
5 Correct 3 ms 82652 KB Output is correct
6 Correct 4 ms 82652 KB Output is correct
7 Correct 2 ms 82652 KB Output is correct
8 Correct 3 ms 82652 KB Output is correct
9 Correct 3 ms 82652 KB Output is correct
10 Correct 3 ms 82652 KB Output is correct
11 Correct 3 ms 82652 KB Output is correct
12 Correct 1462 ms 85300 KB Output is correct
13 Correct 536 ms 89588 KB Output is correct
14 Correct 2927 ms 90976 KB Output is correct
15 Correct 3082 ms 95588 KB Output is correct
16 Correct 1998 ms 98988 KB Output is correct
17 Correct 2957 ms 104640 KB Output is correct
18 Correct 2640 ms 108944 KB Output is correct
19 Correct 1907 ms 120756 KB Output is correct
20 Correct 7850 ms 120756 KB Output is correct
21 Correct 1260 ms 120756 KB Output is correct
22 Correct 8560 ms 129144 KB Output is correct
23 Correct 795 ms 135272 KB Output is correct
24 Correct 4604 ms 137020 KB Output is correct
25 Correct 8694 ms 145908 KB Output is correct
26 Correct 6943 ms 151216 KB Output is correct
27 Correct 7271 ms 156052 KB Output is correct
28 Correct 2116 ms 183720 KB Output is correct
29 Correct 2923 ms 196948 KB Output is correct
30 Correct 10201 ms 198484 KB Output is correct
31 Correct 9039 ms 200076 KB Output is correct
32 Correct 1807 ms 200076 KB Output is correct
33 Correct 2773 ms 202860 KB Output is correct
34 Correct 721 ms 233252 KB Output is correct
35 Correct 5147 ms 233252 KB Output is correct
36 Correct 9458 ms 254044 KB Output is correct
37 Correct 7422 ms 264572 KB Output is correct
38 Correct 8374 ms 274808 KB Output is correct
39 Correct 6825 ms 279744 KB Output is correct
40 Correct 2 ms 279744 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 279744 KB Output is correct
2 Correct 4 ms 279744 KB Output is correct
3 Correct 4 ms 279744 KB Output is correct
4 Correct 2 ms 279744 KB Output is correct
5 Correct 2 ms 279744 KB Output is correct
6 Correct 3 ms 279744 KB Output is correct
7 Correct 2 ms 279744 KB Output is correct
8 Correct 2 ms 279744 KB Output is correct
9 Correct 3 ms 279744 KB Output is correct
10 Correct 2 ms 279744 KB Output is correct
11 Correct 3 ms 279744 KB Output is correct
12 Correct 1291 ms 279744 KB Output is correct
13 Correct 528 ms 279744 KB Output is correct
14 Correct 2735 ms 279744 KB Output is correct
15 Correct 3147 ms 280780 KB Output is correct
16 Correct 2059 ms 284264 KB Output is correct
17 Correct 3000 ms 289784 KB Output is correct
18 Correct 2681 ms 294172 KB Output is correct
19 Correct 1907 ms 305620 KB Output is correct
20 Correct 8277 ms 305620 KB Output is correct
21 Correct 1365 ms 305620 KB Output is correct
22 Correct 8882 ms 314352 KB Output is correct
23 Correct 813 ms 320436 KB Output is correct
24 Correct 4626 ms 322016 KB Output is correct
25 Correct 8373 ms 330976 KB Output is correct
26 Correct 7015 ms 336376 KB Output is correct
27 Correct 7394 ms 341120 KB Output is correct
28 Correct 2155 ms 368984 KB Output is correct
29 Correct 2975 ms 382072 KB Output is correct
30 Correct 10142 ms 383540 KB Output is correct
31 Correct 9046 ms 385156 KB Output is correct
32 Correct 2125 ms 385156 KB Output is correct
33 Correct 2919 ms 387072 KB Output is correct
34 Correct 923 ms 387072 KB Output is correct
35 Correct 5080 ms 387072 KB Output is correct
36 Correct 9406 ms 387072 KB Output is correct
37 Correct 7596 ms 387072 KB Output is correct
38 Correct 8439 ms 387072 KB Output is correct
39 Correct 2970 ms 387072 KB Output is correct
40 Correct 4770 ms 387072 KB Output is correct
41 Execution timed out 13014 ms 387072 KB Time limit exceeded
42 Halted 0 ms 0 KB -