oj.uz

Submission #29946

# Submission time Handle Problem Language Result Execution time Memory
29946 2017-07-21T11:18:56 Z osmanorhan Game (IOI13_game) C++14
80 / 100
 8843 ms 236400 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;
    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;
    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 826 ms 236400 KB Output is correct
5 Correct 556 ms 236400 KB Output is correct
6 Correct 823 ms 236400 KB Output is correct
7 Correct 1069 ms 236400 KB Output is correct
8 Correct 643 ms 236400 KB Output is correct
9 Correct 916 ms 236400 KB Output is correct
10 Correct 813 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 1343 ms 236400 KB Output is correct
13 Correct 3026 ms 236400 KB Output is correct
14 Correct 449 ms 236400 KB Output is correct
15 Correct 3659 ms 236400 KB Output is correct
16 Correct 349 ms 236400 KB Output is correct
17 Correct 1606 ms 236400 KB Output is correct
18 Correct 2829 ms 236400 KB Output is correct
19 Correct 2209 ms 236400 KB Output is correct
20 Correct 2113 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 853 ms 236400 KB Output is correct
13 Correct 559 ms 236400 KB Output is correct
14 Correct 863 ms 236400 KB Output is correct
15 Correct 1059 ms 236400 KB Output is correct
16 Correct 723 ms 236400 KB Output is correct
17 Correct 1046 ms 236400 KB Output is correct
18 Correct 743 ms 236400 KB Output is correct
19 Correct 1319 ms 236400 KB Output is correct
20 Correct 2993 ms 236400 KB Output is correct
21 Correct 406 ms 236400 KB Output is correct
22 Correct 3516 ms 236400 KB Output is correct
23 Correct 273 ms 236400 KB Output is correct
24 Correct 1613 ms 236400 KB Output is correct
25 Correct 2859 ms 236400 KB Output is correct
26 Correct 2243 ms 236400 KB Output is correct
27 Correct 2096 ms 236400 KB Output is correct
28 Correct 1289 ms 236400 KB Output is correct
29 Correct 3399 ms 236400 KB Output is correct
30 Correct 8843 ms 236400 KB Output is correct
31 Correct 8053 ms 236400 KB Output is correct
32 Correct 913 ms 236400 KB Output is correct
33 Correct 1286 ms 236400 KB Output is correct
34 Correct 639 ms 236400 KB Output is correct
35 Correct 2846 ms 236400 KB Output is correct
36 Correct 4673 ms 236400 KB Output is correct
37 Correct 4353 ms 236400 KB Output is correct
38 Correct 3913 ms 236400 KB Output is correct
39 Correct 3433 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 836 ms 236400 KB Output is correct
13 Correct 489 ms 236400 KB Output is correct
14 Correct 826 ms 236400 KB Output is correct
15 Correct 956 ms 236400 KB Output is correct
16 Correct 646 ms 236400 KB Output is correct
17 Correct 856 ms 236400 KB Output is correct
18 Correct 879 ms 236400 KB Output is correct
19 Correct 1296 ms 236400 KB Output is correct
20 Correct 2909 ms 236400 KB Output is correct
21 Correct 439 ms 236400 KB Output is correct
22 Correct 3496 ms 236400 KB Output is correct
23 Correct 349 ms 236400 KB Output is correct
24 Correct 1753 ms 236400 KB Output is correct
25 Correct 2783 ms 236400 KB Output is correct
26 Correct 2336 ms 236400 KB Output is correct
27 Correct 1619 ms 236400 KB Output is correct
28 Correct 1299 ms 236400 KB Output is correct
29 Correct 2989 ms 236400 KB Output is correct
30 Correct 8699 ms 236400 KB Output is correct
31 Correct 8109 ms 236400 KB Output is correct
32 Correct 806 ms 236400 KB Output is correct
33 Correct 1196 ms 236400 KB Output is correct
34 Correct 653 ms 236400 KB Output is correct
35 Correct 2583 ms 236400 KB Output is correct
36 Correct 4926 ms 236400 KB Output is correct
37 Correct 3169 ms 236400 KB Output is correct
38 Correct 3836 ms 236400 KB Output is correct
39 Runtime error 736 ms 236400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -