oj.uz

Submission #224967

# Submission time Handle Problem Language Result Execution time Memory
224967 2020-04-19T07:27:10 Z T0p_ Game (IOI13_game) C++14
37 / 100
 1724 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) {
    seg->extend();
    if(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) {
    seg->extend();
    if(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 7 ms 896 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 304 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 942 ms 48412 KB Output is correct
5 Correct 561 ms 35448 KB Output is correct
6 Correct 1173 ms 146168 KB Output is correct
7 Correct 1202 ms 145760 KB Output is correct
8 Correct 1041 ms 143868 KB Output is correct
9 Correct 1168 ms 147704 KB Output is correct
10 Correct 1096 ms 145400 KB Output is correct
11 Correct 5 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 896 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 1059 ms 46200 KB Output is correct
13 Correct 1456 ms 20564 KB Output is correct
14 Correct 775 ms 7996 KB Output is correct
15 Correct 1689 ms 29760 KB Output is correct
16 Correct 300 ms 62456 KB Output is correct
17 Runtime error 1208 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 5 ms 384 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 640 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 928 ms 48608 KB Output is correct
13 Correct 569 ms 35576 KB Output is correct
14 Correct 1157 ms 146168 KB Output is correct
15 Correct 1173 ms 145788 KB Output is correct
16 Correct 1038 ms 144120 KB Output is correct
17 Correct 1148 ms 147776 KB Output is correct
18 Correct 1103 ms 145520 KB Output is correct
19 Correct 1090 ms 46068 KB Output is correct
20 Correct 1458 ms 20556 KB Output is correct
21 Correct 752 ms 8056 KB Output is correct
22 Correct 1667 ms 29688 KB Output is correct
23 Correct 294 ms 62456 KB Output is correct
24 Runtime error 1213 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 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 6 ms 896 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 5 ms 384 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 640 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 928 ms 48632 KB Output is correct
13 Correct 562 ms 35580 KB Output is correct
14 Correct 1145 ms 146040 KB Output is correct
15 Correct 1193 ms 145656 KB Output is correct
16 Correct 1045 ms 143992 KB Output is correct
17 Correct 1167 ms 147832 KB Output is correct
18 Correct 1127 ms 145408 KB Output is correct
19 Correct 1048 ms 46168 KB Output is correct
20 Correct 1470 ms 20472 KB Output is correct
21 Correct 781 ms 8116 KB Output is correct
22 Correct 1724 ms 29676 KB Output is correct
23 Correct 308 ms 62456 KB Output is correct
24 Runtime error 1254 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -