oj.uz

Submission #224937

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

long long _R, _C;

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

struct node1
{
    long long l, r;
    node2 *now;
    node1 *L, *R;
    node1(long long a, long long b, long long c, long long d)
    {
        l = a;
        r = b;
        now = new node2(c, d);
        L = R = NULL;
    }
    void extend()
    {
        if(!L && l != r)
        {
            long long mid = (l+r)>>1ll;
            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) {
    _R = R, _C = C;
    root = new node1(1, R, 1, C);
}

void update2(node2 *seg, long long 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, long long 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, long long p, long long 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) {
    long long p = P+1, q = Q+1;
    update1(root, p, q, K);
}

long long query2(node2 *seg, long long a, long long 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, long long a, long long b, long long c, long long 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) {
    long long p = P+1, q = Q+1, u = U+1, v = V+1;
    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 384 KB Output is correct
2 Correct 6 ms 1152 KB Output is correct
3 Correct 8 ms 1152 KB Output is correct
4 Correct 6 ms 384 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 5 ms 896 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 6 ms 256 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 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 1218 ms 67652 KB Output is correct
5 Correct 668 ms 59208 KB Output is correct
6 Correct 1482 ms 145016 KB Output is correct
7 Correct 1370 ms 144632 KB Output is correct
8 Correct 1215 ms 142200 KB Output is correct
9 Correct 1332 ms 146016 KB Output is correct
10 Correct 1327 ms 144248 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 4 ms 256 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 6 ms 1024 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 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 1307 ms 70996 KB Output is correct
13 Correct 1553 ms 27540 KB Output is correct
14 Correct 950 ms 8568 KB Output is correct
15 Correct 1855 ms 44664 KB Output is correct
16 Correct 374 ms 114424 KB Output is correct
17 Runtime error 1016 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 1152 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 768 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 512 KB Output is correct
12 Correct 1261 ms 67552 KB Output is correct
13 Correct 638 ms 59256 KB Output is correct
14 Correct 1359 ms 145144 KB Output is correct
15 Correct 1387 ms 144816 KB Output is correct
16 Correct 1175 ms 142072 KB Output is correct
17 Correct 1331 ms 146168 KB Output is correct
18 Correct 1312 ms 144240 KB Output is correct
19 Correct 1294 ms 70876 KB Output is correct
20 Correct 1542 ms 27704 KB Output is correct
21 Correct 936 ms 8344 KB Output is correct
22 Correct 1818 ms 44432 KB Output is correct
23 Correct 377 ms 114312 KB Output is correct
24 Runtime error 1020 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 384 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 768 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 1024 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 1181 ms 67416 KB Output is correct
13 Correct 647 ms 59256 KB Output is correct
14 Correct 1461 ms 144908 KB Output is correct
15 Correct 1433 ms 144736 KB Output is correct
16 Correct 1242 ms 142028 KB Output is correct
17 Correct 1564 ms 146176 KB Output is correct
18 Correct 1383 ms 144224 KB Output is correct
19 Correct 1379 ms 70960 KB Output is correct
20 Correct 1685 ms 27308 KB Output is correct
21 Correct 1062 ms 8460 KB Output is correct
22 Correct 1862 ms 44676 KB Output is correct
23 Correct 421 ms 114424 KB Output is correct
24 Runtime error 1020 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -