oj.uz

Submission #27241

# Submission time Handle Problem Language Result Execution time Memory
27241 2017-07-11T11:54:52 Z tlwpdus Game (IOI13_game) C++11
63 / 100
 3416 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>

typedef long long ll;

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ll R, C;
int x, y; ll val;
int sx, sy, ex, ey;

struct node1 {
    ll val;
    node1 *l, *r;
    node1() {val = 0; l = r = NULL;}
    void mer() {val = gcd2(l?l->val:0,r?r->val:0);}
    void upd(int s = 0, int e = C-1) {
        if (s==e) {
            val = ::val;
            return;
        }
        int m = (s+e)>>1;
        if (y<=m) {
            if (!l) l = new node1();
            l->upd(s,m);
        }
        else {
            if (!r) r = new node1();
            r->upd(m+1,e);
        }
        mer();
    }
    void upd(node1 *a, node1 *b, int s = 0, int e = C-1) {
        if (s==e) {
            val = gcd2(a?a->val:0,b?b->val:0);
            return;
        }
        int m = (s+e)>>1;
        if (y<=m) {
            if (!l) l = new node1();
            l->upd(a?a->l:0,b?b->l:0,s,m);
        }
        else {
            if (!r) r = new node1();
            r->upd(a?a->r:0,b?b->r:0,m+1,e);
        }
        mer();
    }
    ll getv(int s = 0, int e = C-1) {
        if (e<sy||ey<s) return 0;
        if (sy<=s&&e<=ey) return val;
        int m = (s+e)>>1;
        return gcd2(l?l->getv(s,m):0,r?r->getv(m+1,e):0);
    }
};

struct node2 {
    node1 *head;
    node2 *l, *r;
    node2() {head = new node1(); l = r = NULL;}
    void mer() {
        head->upd(l?l->head:0,r?r->head:0);
    }
    void upd(int s = 0, int e = R-1) {
        head->upd();
        if (s==e) return;
        int m = (s+e)>>1;
        if (x<=m) {
            if (!l) l = new node2();
            l -> upd(s,m);
        }
        else {
            if (!r) r = new node2();
            r -> upd(m+1,e);
        }
        mer();
    }
    ll getv(int s = 0, int e = R-1) {
        if (e<sx||ex<s) return 0;
        if (sx<=s&&e<=ex) return head->getv();
        int m = (s+e)>>1;
        return gcd2(l?l->getv(s,m):0,r?r->getv(m+1,e):0);
    }
} *tree;

void upd(int x, int y, ll val) {
    ::x = x; ::y = y; ::val = val;
    tree->upd();
}

ll calc(int sx, int sy, int ex, int ey) {
    ::sx=sx;::ex=ex;::sy=sy;::ey=ey;
    return tree->getv();
}

void init(int R, int C) {
    ::R = R; ::C = C;
    tree = new node2();
}

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

ll calculate(int P, int Q, int U, int V) {
    return calc(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 0 ms 2076 KB Output is correct
2 Correct 0 ms 2208 KB Output is correct
3 Correct 0 ms 2208 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 0 ms 2208 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2208 KB Output is correct
10 Correct 0 ms 2076 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct
12 Correct 0 ms 2076 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2076 KB Output is correct
3 Correct 0 ms 2076 KB Output is correct
4 Correct 879 ms 10392 KB Output is correct
5 Correct 583 ms 10392 KB Output is correct
6 Correct 1029 ms 10524 KB Output is correct
7 Correct 1079 ms 10524 KB Output is correct
8 Correct 703 ms 6828 KB Output is correct
9 Correct 1056 ms 10656 KB Output is correct
10 Correct 999 ms 10524 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2208 KB Output is correct
3 Correct 0 ms 2208 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 0 ms 2208 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2208 KB Output is correct
10 Correct 0 ms 2076 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct
12 Correct 1263 ms 13560 KB Output is correct
13 Correct 2916 ms 7224 KB Output is correct
14 Correct 446 ms 2208 KB Output is correct
15 Correct 3416 ms 9732 KB Output is correct
16 Correct 399 ms 19236 KB Output is correct
17 Correct 1816 ms 11976 KB Output is correct
18 Correct 3169 ms 19236 KB Output is correct
19 Correct 2796 ms 19368 KB Output is correct
20 Correct 2333 ms 19236 KB Output is correct
21 Correct 0 ms 2076 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2208 KB Output is correct
3 Correct 0 ms 2208 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 0 ms 2208 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2208 KB Output is correct
10 Correct 0 ms 2076 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct
12 Correct 846 ms 10392 KB Output is correct
13 Correct 563 ms 10392 KB Output is correct
14 Correct 939 ms 10524 KB Output is correct
15 Correct 1213 ms 10524 KB Output is correct
16 Correct 736 ms 6828 KB Output is correct
17 Correct 1136 ms 10656 KB Output is correct
18 Correct 956 ms 10524 KB Output is correct
19 Correct 1233 ms 13560 KB Output is correct
20 Correct 2853 ms 7224 KB Output is correct
21 Correct 526 ms 2208 KB Output is correct
22 Correct 3303 ms 9732 KB Output is correct
23 Correct 379 ms 19236 KB Output is correct
24 Correct 1709 ms 11976 KB Output is correct
25 Correct 2993 ms 19236 KB Output is correct
26 Correct 2706 ms 19368 KB Output is correct
27 Correct 2226 ms 19236 KB Output is correct
28 Correct 1439 ms 252348 KB Output is correct
29 Memory limit exceeded 2889 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2208 KB Output is correct
3 Correct 0 ms 2208 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 0 ms 2208 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2208 KB Output is correct
10 Correct 0 ms 2076 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct
12 Correct 886 ms 10392 KB Output is correct
13 Correct 553 ms 10392 KB Output is correct
14 Correct 959 ms 10524 KB Output is correct
15 Correct 1106 ms 10524 KB Output is correct
16 Correct 669 ms 6828 KB Output is correct
17 Correct 1169 ms 10656 KB Output is correct
18 Correct 1016 ms 10524 KB Output is correct
19 Correct 1336 ms 13560 KB Output is correct
20 Correct 2906 ms 7224 KB Output is correct
21 Correct 516 ms 2208 KB Output is correct
22 Correct 3359 ms 9732 KB Output is correct
23 Correct 449 ms 19236 KB Output is correct
24 Correct 1923 ms 11976 KB Output is correct
25 Correct 2616 ms 19236 KB Output is correct
26 Correct 2736 ms 19368 KB Output is correct
27 Correct 2369 ms 19236 KB Output is correct
28 Correct 1693 ms 252348 KB Output is correct
29 Memory limit exceeded 3143 ms 256000 KB Memory limit exceeded
30 Halted 0 ms 0 KB -