oj.uz

Submission #224975

# Submission time Handle Problem Language Result Execution time Memory
224975 2020-04-19T07:32:14 Z T0p_ Game (IOI13_game) C++14
63 / 100
 2129 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int _R, _C;

struct node2
{
    long long v;
    node2 *L, *R;
    node2()
    {
        v = 0;
        L = R = NULL;
    }
    void extend()
    {
        if(!L)
        {
            L = new node2();
            R = new node2();
        } 
    }
};

struct node1
{
    node2 *now;
    node1 *L, *R;
    node1()
    {
        now = new node2();
        L = R = NULL;
    }    
    void extend()
    {
        if(!L)
        {
            L = new node1();
            R = new node1();
        }
    }
};

node1 *root;

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

void init(int R, int C) {
    _R = R, _C = C;
    root = new node1();
}

void update2(node2 *seg, int l, int r, int p, long long v) {
    seg->extend();
    if(l == r) return void(seg->v = v);
    int mid = (l+r)>>1;
    if(p <= mid) update2(seg->L, l, mid, p, v);
    else update2(seg->R, mid+1, r, p, v);
    seg->v = gcd2(seg->L->v, seg->R->v);
}

void push_seg(node2 *seg, node2 *L, node2 *R, int l, int r, int p) {
    seg->extend();
    L->extend();
    R->extend();
    if(l == r) return void(seg->v = gcd2(L->v, R->v));
    int mid = (l+r)>>1;
    if(p <= mid) push_seg(seg->L, L->L, R->L, l, mid, p);
    else push_seg(seg->R, L->R, R->R, mid+1, r, p);
    seg->v = gcd2(L->v, R->v);
}

void update1(node1 *seg, int l, int r, int p, int _p, long long v) {
    seg->extend();
    if(l == r) return void(update2(seg->now, 1, _C, _p, v));
    int mid = (l+r)>>1;
    if(p <= mid) update1(seg->L, l, mid, p, _p, v);
    else update1(seg->R, mid+1, r, p, _p, v);
    push_seg(seg->now, seg->L->now, seg->R->now, 1, _C, _p);
}

void update(int P, int Q, long long K) {
    P++, Q++;
    update1(root, 1, _R, P, Q, K);
}

long long query2(node2 *seg, int l, int r, int a, int b) {
    if(!seg || r < a || b < l) return 0;
    if(a <= l && r <= b) return seg->v;
    int mid = (l+r)>>1;
    return gcd2(query2(seg->L, l, mid, a, b), query2(seg->R, mid+1, r, a, b));
}

long long query1(node1 *seg, int l, int r, int a, int b, int _a, int _b) {
    if(!seg || r < a || b < l) return 0;
    if(a <= l && r <= b) return query2(seg->now, 1, _C, _a, _b);
    int mid = (l+r)>>1;
    return gcd2(query1(seg->L, l, mid, a, b, _a, _b), query1(seg->R, mid+1, r, a, b, _a, _b));
}

long long calculate(int P, int Q, int U, int V) {
    P++, Q++, U++, V++;
    return query1(root, 1, _R, P, U, Q, 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 5 ms 256 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 697 ms 31232 KB Output is correct
5 Correct 527 ms 31392 KB Output is correct
6 Correct 652 ms 28512 KB Output is correct
7 Correct 735 ms 28240 KB Output is correct
8 Correct 491 ms 17528 KB Output is correct
9 Correct 703 ms 28408 KB Output is correct
10 Correct 680 ms 28024 KB Output is correct
11 Correct 4 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1034 ms 40944 KB Output is correct
13 Correct 1489 ms 16460 KB Output is correct
14 Correct 415 ms 1272 KB Output is correct
15 Correct 1799 ms 25592 KB Output is correct
16 Correct 301 ms 58232 KB Output is correct
17 Correct 1296 ms 40056 KB Output is correct
18 Correct 2098 ms 63952 KB Output is correct
19 Correct 1812 ms 64280 KB Output is correct
20 Correct 1799 ms 63520 KB Output is correct
21 Correct 5 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 717 ms 31180 KB Output is correct
13 Correct 525 ms 31352 KB Output is correct
14 Correct 705 ms 28512 KB Output is correct
15 Correct 773 ms 28128 KB Output is correct
16 Correct 498 ms 17336 KB Output is correct
17 Correct 771 ms 28392 KB Output is correct
18 Correct 748 ms 28024 KB Output is correct
19 Correct 1049 ms 40824 KB Output is correct
20 Correct 1528 ms 16480 KB Output is correct
21 Correct 404 ms 1400 KB Output is correct
22 Correct 1792 ms 25356 KB Output is correct
23 Correct 305 ms 58232 KB Output is correct
24 Correct 1279 ms 40148 KB Output is correct
25 Correct 2093 ms 64304 KB Output is correct
26 Correct 1844 ms 64380 KB Output is correct
27 Correct 1756 ms 63608 KB Output is correct
28 Runtime error 462 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 696 ms 31068 KB Output is correct
13 Correct 523 ms 31532 KB Output is correct
14 Correct 671 ms 28416 KB Output is correct
15 Correct 733 ms 28152 KB Output is correct
16 Correct 477 ms 17272 KB Output is correct
17 Correct 711 ms 28408 KB Output is correct
18 Correct 682 ms 28024 KB Output is correct
19 Correct 1026 ms 40824 KB Output is correct
20 Correct 1479 ms 16456 KB Output is correct
21 Correct 429 ms 1400 KB Output is correct
22 Correct 1779 ms 25336 KB Output is correct
23 Correct 303 ms 58232 KB Output is correct
24 Correct 1287 ms 40240 KB Output is correct
25 Correct 2129 ms 63844 KB Output is correct
26 Correct 1863 ms 64296 KB Output is correct
27 Correct 1751 ms 63528 KB Output is correct
28 Runtime error 473 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -