oj.uz

Submission #225657

# Submission time Handle Problem Language Result Execution time Memory
225657 2020-04-21T06:20:51 Z T0p_ Game (IOI13_game) C++14
63 / 100
 1896 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;
    }
};

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

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

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 c, int d)
{
    if(!seg || r < a || b < l) return 0;
    if(a <= l && r <= b) return query2(seg->now, 1, _C, c, d);
    int mid = (l+r)>>1;
    return gcd2(query1(seg->L, l, mid, a, b, c, d), query1(seg->R, mid+1, r, a, b, c, d));
}

static void update2(node2 *seg, int l, int r, int p, long long k)
{
    if(l == r) return void(seg->v = k);
    int mid = (l+r)>>1;
    if(p <= mid)
    {
        if(!seg->L) seg->L = new node2();
        update2(seg->L, l, mid, p, k);
    }
    else
    {
        if(!seg->R) seg->R = new node2();
        update2(seg->R, mid+1, r, p, k);
    }
    seg->v = gcd2((seg->L) ? seg->L->v : 0,(seg->R) ? seg->R->v : 0);
}

static void update1(node1 *seg, int l, int r, int p, int q, long long k)
{
    if(l == r) return void(update2(seg->now, 1, _C, q, k));
    int mid = (l + r)>>1;
    if(p <= mid)
    {
        if(!seg->L) seg->L = new node1();
        update1(seg->L, l, mid, p, q, k);
    }
    else
    {
        if(!seg->R) seg->R = new node1();
        update1(seg->R, mid+1, r, p, q, k);
    }
    long long v = gcd2((seg->L) ? query2(seg->L->now, 1, _C, q, q) : 0, (seg->R) ? query2(seg->R->now, 1, _C, q, q) : 0);
    update2(seg->now, 1, _C, q, v);
}

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

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

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 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 368 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 589 ms 14968 KB Output is correct
5 Correct 423 ms 15096 KB Output is correct
6 Correct 508 ms 12024 KB Output is correct
7 Correct 553 ms 11896 KB Output is correct
8 Correct 387 ms 8696 KB Output is correct
9 Correct 541 ms 11796 KB Output is correct
10 Correct 502 ms 11332 KB Output is correct
11 Correct 5 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 384 KB Output is correct
3 Correct 5 ms 384 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 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 886 ms 18168 KB Output is correct
13 Correct 1534 ms 8484 KB Output is correct
14 Correct 366 ms 3064 KB Output is correct
15 Correct 1807 ms 11040 KB Output is correct
16 Correct 256 ms 20344 KB Output is correct
17 Correct 820 ms 13688 KB Output is correct
18 Correct 1387 ms 20856 KB Output is correct
19 Correct 1179 ms 21100 KB Output is correct
20 Correct 1131 ms 20344 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 512 KB Output is correct
3 Correct 5 ms 384 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 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 597 ms 14840 KB Output is correct
13 Correct 427 ms 15096 KB Output is correct
14 Correct 498 ms 11960 KB Output is correct
15 Correct 563 ms 11788 KB Output is correct
16 Correct 381 ms 8696 KB Output is correct
17 Correct 532 ms 11836 KB Output is correct
18 Correct 506 ms 11512 KB Output is correct
19 Correct 901 ms 18168 KB Output is correct
20 Correct 1489 ms 8440 KB Output is correct
21 Correct 357 ms 3064 KB Output is correct
22 Correct 1842 ms 11004 KB Output is correct
23 Correct 259 ms 20344 KB Output is correct
24 Correct 829 ms 13824 KB Output is correct
25 Correct 1380 ms 20984 KB Output is correct
26 Correct 1183 ms 21200 KB Output is correct
27 Correct 1092 ms 20344 KB Output is correct
28 Correct 1091 ms 256000 KB Output is correct
29 Runtime error 1896 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 588 ms 14072 KB Output is correct
13 Correct 433 ms 14296 KB Output is correct
14 Correct 500 ms 11256 KB Output is correct
15 Correct 559 ms 10872 KB Output is correct
16 Correct 394 ms 8184 KB Output is correct
17 Correct 537 ms 11040 KB Output is correct
18 Correct 490 ms 10580 KB Output is correct
19 Correct 902 ms 17272 KB Output is correct
20 Correct 1504 ms 7608 KB Output is correct
21 Correct 364 ms 2296 KB Output is correct
22 Correct 1796 ms 10364 KB Output is correct
23 Correct 260 ms 19656 KB Output is correct
24 Correct 834 ms 12852 KB Output is correct
25 Correct 1379 ms 20044 KB Output is correct
26 Correct 1199 ms 20276 KB Output is correct
27 Correct 1106 ms 19452 KB Output is correct
28 Correct 1065 ms 256000 KB Output is correct
29 Runtime error 1871 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -