oj.uz

Submission #29945

# Submission time Handle Problem Language Result Execution time Memory
29945 2017-07-21T11:17:39 Z osmanorhan Game (IOI13_game) C++14
80 / 100
 8693 ms 236404 KB 
#include "game.h"
#include <bits/stdc++.h>
#define all( x ) x.begin(), x.end()
#define ort (b+s)/2
#define fi first
#define se second
#define pb push_back
#define y1 asdaswe
#define y2 asdaswasdf

using namespace std;

const int maxn = 10020;
const int maxm = 10000020;

typedef long long Lint;
typedef pair<int,int> ii;

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

Lint segment[maxm];
int l[maxm], r[maxm], N = 1; // left and right node's index for each node in small segment_trees
int tl[maxm], tr[maxm]; // left and right node's index for each node in big segment_tree
int x, y, row, c;
int x1, x2, y1, y2;
Lint val;

int up2( int n, int b, int s, int tp, int lin, int rin ) {
    if( b > y || s < y ) return n;

    if( n == 0 ) n = ++N, assert( N < 10000000 );
    if( y <= b && s <= y ) {
        if( tp ) segment[n] = val;
        else segment[n] = gcd2( segment[lin], segment[rin] );
        return n;
    }
    l[n] = up2( l[n], b, ort, tp, l[lin], l[rin] );
    r[n] = up2( r[n], ort+1, s, tp, r[lin], r[rin] );
    segment[n] = gcd2( segment[l[n]], segment[r[n]] );
    return n;
}

int up( int n, int b, int s ) {
    if( b > x || s < x ) return n;

    if( n == 0 ) n = ++N, assert( N < 10000000 );
    if( x <= b && s <= x ) {
        up2( n, 0, c-1, 1, 0, 0 );
        return n;
    }
    tl[n] = up( tl[n], b, ort );
    tr[n] = up( tr[n], ort+1, s );
    up2( n, 0, c-1, 0, tl[n], tr[n] );
    return n;
}

Lint get2( int n, int b, int s ) {
    if( !n || b > y2 || s < y1 ) return 0;
    if( y1 <= b && s <= y2 ) return segment[n];
    return gcd2( get2( l[n], b, ort ), get2( r[n], ort+1, s ) );
}

Lint get( int n, int b, int s ) {
    if( !n || b > x2 || s < x1 ) return 0;
    if( x1 <= b && s <= x2 ) return get2( n, 0, c-1 );
    return gcd2( get( tl[n], b, ort ), get( tr[n], ort+1, s ) );
}

void init(int R, int C) {
    row = R;
    c = C;
}

void update(int P, int Q, long long K) {
    x = P;
    y = Q;
    val = K;
    up( 1, 0, row-1 );
}

long long calculate(int P, int Q, int U, int V) {
    x1 = P;
    y1 = Q;
    x2 = U;
    y2 = V;
    return get( 1, 0, row-1 );
}

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 236400 KB Output is correct
2 Correct 0 ms 236400 KB Output is correct
3 Correct 0 ms 236400 KB Output is correct
4 Correct 853 ms 236400 KB Output is correct
5 Correct 576 ms 236400 KB Output is correct
6 Correct 863 ms 236400 KB Output is correct
7 Correct 1012 ms 236400 KB Output is correct
8 Correct 626 ms 236400 KB Output is correct
9 Correct 1059 ms 236400 KB Output is correct
10 Correct 929 ms 236400 KB Output is correct
11 Correct 0 ms 236400 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 236400 KB Output is correct
2 Correct 0 ms 236400 KB Output is correct
3 Correct 0 ms 236400 KB Output is correct
4 Correct 0 ms 236400 KB Output is correct
5 Correct 0 ms 236400 KB Output is correct
6 Correct 0 ms 236400 KB Output is correct
7 Correct 0 ms 236400 KB Output is correct
8 Correct 0 ms 236400 KB Output is correct
9 Correct 0 ms 236400 KB Output is correct
10 Correct 0 ms 236400 KB Output is correct
11 Correct 0 ms 236400 KB Output is correct
12 Correct 1389 ms 236400 KB Output is correct
13 Correct 3033 ms 236400 KB Output is correct
14 Correct 423 ms 236400 KB Output is correct
15 Correct 3493 ms 236400 KB Output is correct
16 Correct 246 ms 236400 KB Output is correct
17 Correct 1216 ms 236400 KB Output is correct
18 Correct 2466 ms 236400 KB Output is correct
19 Correct 2223 ms 236400 KB Output is correct
20 Correct 2045 ms 236400 KB Output is correct
21 Correct 0 ms 236400 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 236400 KB Output is correct
2 Correct 0 ms 236400 KB Output is correct
3 Correct 0 ms 236400 KB Output is correct
4 Correct 0 ms 236400 KB Output is correct
5 Correct 0 ms 236400 KB Output is correct
6 Correct 0 ms 236400 KB Output is correct
7 Correct 0 ms 236400 KB Output is correct
8 Correct 0 ms 236400 KB Output is correct
9 Correct 0 ms 236400 KB Output is correct
10 Correct 0 ms 236400 KB Output is correct
11 Correct 0 ms 236400 KB Output is correct
12 Correct 873 ms 236400 KB Output is correct
13 Correct 566 ms 236400 KB Output is correct
14 Correct 826 ms 236400 KB Output is correct
15 Correct 996 ms 236400 KB Output is correct
16 Correct 599 ms 236400 KB Output is correct
17 Correct 949 ms 236400 KB Output is correct
18 Correct 853 ms 236400 KB Output is correct
19 Correct 1289 ms 236400 KB Output is correct
20 Correct 2943 ms 236400 KB Output is correct
21 Correct 456 ms 236400 KB Output is correct
22 Correct 3556 ms 236400 KB Output is correct
23 Correct 329 ms 236400 KB Output is correct
24 Correct 1573 ms 236400 KB Output is correct
25 Correct 2906 ms 236400 KB Output is correct
26 Correct 2299 ms 236400 KB Output is correct
27 Correct 2243 ms 236400 KB Output is correct
28 Correct 1233 ms 236400 KB Output is correct
29 Correct 3506 ms 236400 KB Output is correct
30 Correct 8493 ms 236400 KB Output is correct
31 Correct 7883 ms 236400 KB Output is correct
32 Correct 869 ms 236400 KB Output is correct
33 Correct 1136 ms 236400 KB Output is correct
34 Correct 606 ms 236400 KB Output is correct
35 Correct 2759 ms 236400 KB Output is correct
36 Correct 5299 ms 236400 KB Output is correct
37 Correct 4393 ms 236400 KB Output is correct
38 Correct 3913 ms 236400 KB Output is correct
39 Correct 3756 ms 236400 KB Output is correct
40 Correct 0 ms 236400 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 236400 KB Output is correct
2 Correct 0 ms 236400 KB Output is correct
3 Correct 0 ms 236400 KB Output is correct
4 Correct 0 ms 236400 KB Output is correct
5 Correct 0 ms 236400 KB Output is correct
6 Correct 0 ms 236400 KB Output is correct
7 Correct 0 ms 236400 KB Output is correct
8 Correct 0 ms 236400 KB Output is correct
9 Correct 0 ms 236400 KB Output is correct
10 Correct 0 ms 236400 KB Output is correct
11 Correct 0 ms 236400 KB Output is correct
12 Correct 879 ms 236400 KB Output is correct
13 Correct 503 ms 236400 KB Output is correct
14 Correct 863 ms 236400 KB Output is correct
15 Correct 846 ms 236400 KB Output is correct
16 Correct 659 ms 236400 KB Output is correct
17 Correct 1016 ms 236400 KB Output is correct
18 Correct 739 ms 236400 KB Output is correct
19 Correct 1383 ms 236400 KB Output is correct
20 Correct 2986 ms 236400 KB Output is correct
21 Correct 453 ms 236400 KB Output is correct
22 Correct 3423 ms 236400 KB Output is correct
23 Correct 319 ms 236400 KB Output is correct
24 Correct 1593 ms 236400 KB Output is correct
25 Correct 2889 ms 236400 KB Output is correct
26 Correct 2319 ms 236400 KB Output is correct
27 Correct 2079 ms 236400 KB Output is correct
28 Correct 1316 ms 236400 KB Output is correct
29 Correct 3503 ms 236400 KB Output is correct
30 Correct 8693 ms 236400 KB Output is correct
31 Correct 7779 ms 236400 KB Output is correct
32 Correct 899 ms 236400 KB Output is correct
33 Correct 1229 ms 236400 KB Output is correct
34 Correct 663 ms 236400 KB Output is correct
35 Correct 2653 ms 236400 KB Output is correct
36 Correct 5163 ms 236400 KB Output is correct
37 Correct 4616 ms 236400 KB Output is correct
38 Correct 4253 ms 236400 KB Output is correct
39 Runtime error 876 ms 236404 KB Execution killed because of forbidden syscall gettid (186)
40 Halted 0 ms 0 KB -