oj.uz

Submission #29981

# Submission time Handle Problem Language Result Execution time Memory
29981 2017-07-21T11:36:14 Z osmanorhan Game (IOI13_game) C++14
80 / 100
 8589 ms 244656 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 = 22020;
const int maxm = 15000020;

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[maxn*32], tr[maxn*32], N2 = 1; // left and right node's index for each node in big segment_tree
int in[maxn*32];
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( N >= 15000000 ) exit(0);}
    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 = ++N2;
    if( in[n] == 0 ) {in[n] = ++N; if( N >= 15000000 ) exit(0);}
    if( x <= b && s <= x ) {
        up2( in[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( in[n], 0, c-1, 0, in[tl[n]], in[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( in[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 244656 KB Output is correct
2 Correct 0 ms 244656 KB Output is correct
3 Correct 0 ms 244656 KB Output is correct
4 Correct 0 ms 244656 KB Output is correct
5 Correct 0 ms 244656 KB Output is correct
6 Correct 0 ms 244656 KB Output is correct
7 Correct 0 ms 244656 KB Output is correct
8 Correct 0 ms 244656 KB Output is correct
9 Correct 0 ms 244656 KB Output is correct
10 Correct 0 ms 244656 KB Output is correct
11 Correct 0 ms 244656 KB Output is correct
12 Correct 0 ms 244656 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 244656 KB Output is correct
2 Correct 0 ms 244656 KB Output is correct
3 Correct 0 ms 244656 KB Output is correct
4 Correct 833 ms 244656 KB Output is correct
5 Correct 486 ms 244656 KB Output is correct
6 Correct 843 ms 244656 KB Output is correct
7 Correct 1123 ms 244656 KB Output is correct
8 Correct 653 ms 244656 KB Output is correct
9 Correct 1056 ms 244656 KB Output is correct
10 Correct 889 ms 244656 KB Output is correct
11 Correct 0 ms 244656 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 244656 KB Output is correct
2 Correct 0 ms 244656 KB Output is correct
3 Correct 0 ms 244656 KB Output is correct
4 Correct 0 ms 244656 KB Output is correct
5 Correct 0 ms 244656 KB Output is correct
6 Correct 0 ms 244656 KB Output is correct
7 Correct 0 ms 244656 KB Output is correct
8 Correct 0 ms 244656 KB Output is correct
9 Correct 0 ms 244656 KB Output is correct
10 Correct 0 ms 244656 KB Output is correct
11 Correct 0 ms 244656 KB Output is correct
12 Correct 1416 ms 244656 KB Output is correct
13 Correct 2966 ms 244656 KB Output is correct
14 Correct 463 ms 244656 KB Output is correct
15 Correct 3456 ms 244656 KB Output is correct
16 Correct 313 ms 244656 KB Output is correct
17 Correct 1486 ms 244656 KB Output is correct
18 Correct 2623 ms 244656 KB Output is correct
19 Correct 1989 ms 244656 KB Output is correct
20 Correct 2053 ms 244656 KB Output is correct
21 Correct 0 ms 244656 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 244656 KB Output is correct
2 Correct 0 ms 244656 KB Output is correct
3 Correct 0 ms 244656 KB Output is correct
4 Correct 0 ms 244656 KB Output is correct
5 Correct 0 ms 244656 KB Output is correct
6 Correct 0 ms 244656 KB Output is correct
7 Correct 0 ms 244656 KB Output is correct
8 Correct 0 ms 244656 KB Output is correct
9 Correct 0 ms 244656 KB Output is correct
10 Correct 0 ms 244656 KB Output is correct
11 Correct 0 ms 244656 KB Output is correct
12 Correct 826 ms 244656 KB Output is correct
13 Correct 466 ms 244656 KB Output is correct
14 Correct 856 ms 244656 KB Output is correct
15 Correct 999 ms 244656 KB Output is correct
16 Correct 646 ms 244656 KB Output is correct
17 Correct 933 ms 244656 KB Output is correct
18 Correct 683 ms 244656 KB Output is correct
19 Correct 1199 ms 244656 KB Output is correct
20 Correct 2843 ms 244656 KB Output is correct
21 Correct 466 ms 244656 KB Output is correct
22 Correct 3316 ms 244656 KB Output is correct
23 Correct 289 ms 244656 KB Output is correct
24 Correct 1649 ms 244656 KB Output is correct
25 Correct 2203 ms 244656 KB Output is correct
26 Correct 1599 ms 244656 KB Output is correct
27 Correct 2173 ms 244656 KB Output is correct
28 Correct 1363 ms 244656 KB Output is correct
29 Correct 3109 ms 244656 KB Output is correct
30 Correct 8276 ms 244656 KB Output is correct
31 Correct 8316 ms 244656 KB Output is correct
32 Correct 906 ms 244656 KB Output is correct
33 Correct 1056 ms 244656 KB Output is correct
34 Correct 533 ms 244656 KB Output is correct
35 Correct 2649 ms 244656 KB Output is correct
36 Correct 6033 ms 244656 KB Output is correct
37 Correct 3216 ms 244656 KB Output is correct
38 Correct 3506 ms 244656 KB Output is correct
39 Correct 2913 ms 244656 KB Output is correct
40 Correct 0 ms 244656 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 244656 KB Output is correct
2 Correct 0 ms 244656 KB Output is correct
3 Correct 0 ms 244656 KB Output is correct
4 Correct 0 ms 244656 KB Output is correct
5 Correct 0 ms 244656 KB Output is correct
6 Correct 0 ms 244656 KB Output is correct
7 Correct 0 ms 244656 KB Output is correct
8 Correct 0 ms 244656 KB Output is correct
9 Correct 0 ms 244656 KB Output is correct
10 Correct 0 ms 244656 KB Output is correct
11 Correct 0 ms 244656 KB Output is correct
12 Correct 893 ms 244656 KB Output is correct
13 Correct 559 ms 244656 KB Output is correct
14 Correct 943 ms 244656 KB Output is correct
15 Correct 1069 ms 244656 KB Output is correct
16 Correct 679 ms 244656 KB Output is correct
17 Correct 1096 ms 244656 KB Output is correct
18 Correct 909 ms 244656 KB Output is correct
19 Correct 1399 ms 244656 KB Output is correct
20 Correct 3046 ms 244656 KB Output is correct
21 Correct 476 ms 244656 KB Output is correct
22 Correct 3649 ms 244656 KB Output is correct
23 Correct 323 ms 244656 KB Output is correct
24 Correct 1603 ms 244656 KB Output is correct
25 Correct 3073 ms 244656 KB Output is correct
26 Correct 2616 ms 244656 KB Output is correct
27 Correct 2256 ms 244656 KB Output is correct
28 Correct 1316 ms 244656 KB Output is correct
29 Correct 3466 ms 244656 KB Output is correct
30 Correct 8589 ms 244656 KB Output is correct
31 Correct 7169 ms 244656 KB Output is correct
32 Correct 773 ms 244656 KB Output is correct
33 Correct 1146 ms 244656 KB Output is correct
34 Correct 663 ms 244656 KB Output is correct
35 Correct 2259 ms 244656 KB Output is correct
36 Correct 4499 ms 244656 KB Output is correct
37 Correct 4219 ms 244656 KB Output is correct
38 Correct 4126 ms 244656 KB Output is correct
39 Incorrect 1476 ms 244656 KB Output isn't correct
40 Halted 0 ms 0 KB -