oj.uz

Submission #225656

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

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

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 256 KB Output is correct
2 Correct 6 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 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 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 128 KB Output is correct
4 Correct 593 ms 17272 KB Output is correct
5 Correct 434 ms 16888 KB Output is correct
6 Correct 504 ms 14708 KB Output is correct
7 Correct 570 ms 14584 KB Output is correct
8 Correct 396 ms 11000 KB Output is correct
9 Correct 540 ms 14456 KB Output is correct
10 Correct 502 ms 14204 KB Output is correct
11 Correct 5 ms 384 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 5 ms 256 KB Output is correct
5 Correct 5 ms 384 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 897 ms 20064 KB Output is correct
13 Correct 1524 ms 10352 KB Output is correct
14 Correct 349 ms 5752 KB Output is correct
15 Correct 1806 ms 13520 KB Output is correct
16 Correct 260 ms 22520 KB Output is correct
17 Correct 828 ms 16504 KB Output is correct
18 Correct 1388 ms 24084 KB Output is correct
19 Correct 1179 ms 24364 KB Output is correct
20 Correct 1110 ms 23800 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 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 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 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 594 ms 17112 KB Output is correct
13 Correct 424 ms 17096 KB Output is correct
14 Correct 504 ms 14600 KB Output is correct
15 Correct 545 ms 14456 KB Output is correct
16 Correct 391 ms 10872 KB Output is correct
17 Correct 541 ms 14456 KB Output is correct
18 Correct 501 ms 13948 KB Output is correct
19 Correct 911 ms 20088 KB Output is correct
20 Correct 1524 ms 10292 KB Output is correct
21 Correct 356 ms 5684 KB Output is correct
22 Correct 1756 ms 13560 KB Output is correct
23 Correct 255 ms 22520 KB Output is correct
24 Correct 805 ms 16512 KB Output is correct
25 Correct 1375 ms 24184 KB Output is correct
26 Correct 1199 ms 24440 KB Output is correct
27 Correct 1108 ms 23552 KB Output is correct
28 Correct 1090 ms 256000 KB Output is correct
29 Runtime error 1906 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 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 384 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 596 ms 17152 KB Output is correct
13 Correct 442 ms 16888 KB Output is correct
14 Correct 515 ms 14712 KB Output is correct
15 Correct 548 ms 14360 KB Output is correct
16 Correct 385 ms 10872 KB Output is correct
17 Correct 547 ms 14584 KB Output is correct
18 Correct 498 ms 14176 KB Output is correct
19 Correct 887 ms 20088 KB Output is correct
20 Correct 1493 ms 10360 KB Output is correct
21 Correct 346 ms 5752 KB Output is correct
22 Correct 1789 ms 13456 KB Output is correct
23 Correct 259 ms 22520 KB Output is correct
24 Correct 865 ms 16504 KB Output is correct
25 Correct 1455 ms 24184 KB Output is correct
26 Correct 1192 ms 24192 KB Output is correct
27 Correct 1097 ms 23744 KB Output is correct
28 Correct 1101 ms 256000 KB Output is correct
29 Runtime error 1874 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -