oj.uz

Submission #224931

# Submission time Handle Problem Language Result Execution time Memory
224931 2020-04-19T06:30:22 Z T0p_ Game (IOI13_game) C++14
37 / 100
 1910 ms 256004 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;

int _C;

struct node2
{
    int l, r;
    long long v;
    node2 *L, *R;
    node2(int a, int b)
    {
        l = a;
        r = b;
        v = 0;
        L = R = NULL;
    }  
    void extend()
    {
        if(!L && l != r)
        {
            int mid = (l+r)>>1;
            L = new node2(l, mid);
            R = new node2(mid+1, r);
        }
    }
};

struct node1
{
    int l, r;
    node2 *now;
    node1 *L, *R;
    node1(int a, int b, int c, int d)
    {
        l = a;
        r = b;
        now = new node2(c, d);
        L = R = NULL;
    }
    void extend()
    {
        if(!L && l != r)
        {
            int mid = (l+r)>>1;
            L = new node1(l, mid, 1, _C);
            R = new node1(mid+1, r, 1, _C);
        }
    }
};

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) {
    _C = C;
    root = new node1(1, R, 1, C);
}

void update2(node2 *seg, int p, long long k) {
    seg->extend();
    if(!(seg->l <= p && p <= seg->r)) return ;
    if(seg->l == seg->r) return void(seg->v = k);
    update2(seg->L, p, k);
    update2(seg->R, p, k);
    seg->v = gcd2(seg->L->v, seg->R->v);
}

void backtrack(node2 *seg, node2 *Lseg, node2 *Rseg, int p) {
    seg->extend();
    Lseg->extend();
    Rseg->extend();
    if(!(seg->l <= p && p <= seg->r)) return ;
    if(seg->l == seg->r) return void(seg->v = gcd2(Lseg->v, Rseg->v));
    backtrack(seg->L, Lseg->L, Rseg->L, p);
    backtrack(seg->R, Lseg->R, Rseg->R, p);
    seg->v = gcd2(Lseg->v, Rseg->v);
}

void update1(node1 *seg, int p, int q, long long k) {
    seg->extend();
    if(!(seg->l <= p && p <= seg->r)) return ;
    if(seg->l == seg->r) return void(update2(seg->now, q, k));
    update1(seg->L, p, q, k);
    update1(seg->R, p, q, k);
    backtrack(seg->now, seg->L->now, seg->R->now, q);
}

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

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

long long query1(node1 *seg, int a, int b, int c, int d) {
    seg->extend();
    if(seg->r < a || b < seg->l) return 0;
    if(a <= seg->l && seg->r <= b) return query2(seg->now, c, d);
    return gcd2(query1(seg->L, a, b, c, d), query1(seg->R, a, b, c, d));
}

long long calculate(int P, int Q, int U, int V) {
    P++, Q++, U++, V++;
    return query1(root, 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 1024 KB Output is correct
3 Correct 6 ms 1024 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 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 6 ms 896 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 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 1144 ms 67380 KB Output is correct
5 Correct 634 ms 59128 KB Output is correct
6 Correct 1549 ms 145016 KB Output is correct
7 Correct 1362 ms 144888 KB Output is correct
8 Correct 1229 ms 142328 KB Output is correct
9 Correct 1376 ms 146252 KB Output is correct
10 Correct 1285 ms 144252 KB Output is correct
11 Correct 4 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 1152 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1301 ms 71068 KB Output is correct
13 Correct 1586 ms 27640 KB Output is correct
14 Correct 965 ms 8312 KB Output is correct
15 Correct 1887 ms 44624 KB Output is correct
16 Correct 363 ms 114288 KB Output is correct
17 Runtime error 1036 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 6 ms 1024 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1173 ms 67456 KB Output is correct
13 Correct 628 ms 59256 KB Output is correct
14 Correct 1372 ms 145224 KB Output is correct
15 Correct 1438 ms 144864 KB Output is correct
16 Correct 1217 ms 142116 KB Output is correct
17 Correct 1362 ms 146308 KB Output is correct
18 Correct 1297 ms 144504 KB Output is correct
19 Correct 1377 ms 70892 KB Output is correct
20 Correct 1592 ms 27592 KB Output is correct
21 Correct 926 ms 8312 KB Output is correct
22 Correct 1860 ms 44664 KB Output is correct
23 Correct 384 ms 114396 KB Output is correct
24 Runtime error 1041 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 7 ms 1024 KB Output is correct
3 Correct 6 ms 1152 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 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1187 ms 67448 KB Output is correct
13 Correct 669 ms 59128 KB Output is correct
14 Correct 1369 ms 145124 KB Output is correct
15 Correct 1403 ms 144772 KB Output is correct
16 Correct 1191 ms 142320 KB Output is correct
17 Correct 1338 ms 146192 KB Output is correct
18 Correct 1286 ms 144368 KB Output is correct
19 Correct 1313 ms 71164 KB Output is correct
20 Correct 1591 ms 27512 KB Output is correct
21 Correct 943 ms 8348 KB Output is correct
22 Correct 1910 ms 44640 KB Output is correct
23 Correct 367 ms 114292 KB Output is correct
24 Runtime error 1043 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -