Submission #29957

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
29957	2017-07-21T11:27:23 Z	osmanorhan	Game (IOI13_game)	C++14	80 / 100	8383 ms	240156 KB

game

#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 = 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( 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( 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	Memory	Grader output
1	Correct	240156 KB	Output is correct
2	Correct	240156 KB	Output is correct
3	Correct	240156 KB	Output is correct
4	Correct	240156 KB	Output is correct
5	Correct	240156 KB	Output is correct
6	Correct	240156 KB	Output is correct
7	Correct	240156 KB	Output is correct
8	Correct	240156 KB	Output is correct
9	Correct	240156 KB	Output is correct
10	Correct	240156 KB	Output is correct
11	Correct	240156 KB	Output is correct
12	Correct	240156 KB	Output is correct

Subtask #2
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	240156 KB	Output is correct
2	Correct	0 ms	240156 KB	Output is correct
3	Correct	0 ms	240156 KB	Output is correct
4	Correct	803 ms	240156 KB	Output is correct
5	Correct	563 ms	240156 KB	Output is correct
6	Correct	696 ms	240156 KB	Output is correct
7	Correct	919 ms	240156 KB	Output is correct
8	Correct	626 ms	240156 KB	Output is correct
9	Correct	1033 ms	240156 KB	Output is correct
10	Correct	879 ms	240156 KB	Output is correct
11	Correct	0 ms	240156 KB	Output is correct

Subtask #3
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	240156 KB	Output is correct
2	Correct	0 ms	240156 KB	Output is correct
3	Correct	0 ms	240156 KB	Output is correct
4	Correct	0 ms	240156 KB	Output is correct
5	Correct	0 ms	240156 KB	Output is correct
6	Correct	0 ms	240156 KB	Output is correct
7	Correct	0 ms	240156 KB	Output is correct
8	Correct	0 ms	240156 KB	Output is correct
9	Correct	0 ms	240156 KB	Output is correct
10	Correct	0 ms	240156 KB	Output is correct
11	Correct	0 ms	240156 KB	Output is correct
12	Correct	1383 ms	240156 KB	Output is correct
13	Correct	2913 ms	240156 KB	Output is correct
14	Correct	456 ms	240156 KB	Output is correct
15	Correct	3606 ms	240156 KB	Output is correct
16	Correct	339 ms	240156 KB	Output is correct
17	Correct	1596 ms	240156 KB	Output is correct
18	Correct	2753 ms	240156 KB	Output is correct
19	Correct	2196 ms	240156 KB	Output is correct
20	Correct	1839 ms	240156 KB	Output is correct
21	Correct	0 ms	240156 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	240156 KB	Output is correct
2	Correct	0 ms	240156 KB	Output is correct
3	Correct	0 ms	240156 KB	Output is correct
4	Correct	0 ms	240156 KB	Output is correct
5	Correct	0 ms	240156 KB	Output is correct
6	Correct	0 ms	240156 KB	Output is correct
7	Correct	0 ms	240156 KB	Output is correct
8	Correct	0 ms	240156 KB	Output is correct
9	Correct	0 ms	240156 KB	Output is correct
10	Correct	0 ms	240156 KB	Output is correct
11	Correct	0 ms	240156 KB	Output is correct
12	Correct	943 ms	240156 KB	Output is correct
13	Correct	526 ms	240156 KB	Output is correct
14	Correct	879 ms	240156 KB	Output is correct
15	Correct	1113 ms	240156 KB	Output is correct
16	Correct	669 ms	240156 KB	Output is correct
17	Correct	899 ms	240156 KB	Output is correct
18	Correct	839 ms	240156 KB	Output is correct
19	Correct	1329 ms	240156 KB	Output is correct
20	Correct	3003 ms	240156 KB	Output is correct
21	Correct	456 ms	240156 KB	Output is correct
22	Correct	3359 ms	240156 KB	Output is correct
23	Correct	309 ms	240156 KB	Output is correct
24	Correct	1349 ms	240156 KB	Output is correct
25	Correct	2019 ms	240156 KB	Output is correct
26	Correct	2433 ms	240156 KB	Output is correct
27	Correct	2116 ms	240156 KB	Output is correct
28	Correct	1193 ms	240156 KB	Output is correct
29	Correct	3299 ms	240156 KB	Output is correct
30	Correct	8233 ms	240156 KB	Output is correct
31	Correct	7963 ms	240156 KB	Output is correct
32	Correct	879 ms	240156 KB	Output is correct
33	Correct	1136 ms	240156 KB	Output is correct
34	Correct	626 ms	240156 KB	Output is correct
35	Correct	2706 ms	240156 KB	Output is correct
36	Correct	5343 ms	240156 KB	Output is correct
37	Correct	3183 ms	240156 KB	Output is correct
38	Correct	3639 ms	240156 KB	Output is correct
39	Correct	2786 ms	240156 KB	Output is correct
40	Correct	0 ms	240156 KB	Output is correct

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	240156 KB	Output is correct
2	Correct	0 ms	240156 KB	Output is correct
3	Correct	0 ms	240156 KB	Output is correct
4	Correct	0 ms	240156 KB	Output is correct
5	Correct	0 ms	240156 KB	Output is correct
6	Correct	0 ms	240156 KB	Output is correct
7	Correct	0 ms	240156 KB	Output is correct
8	Correct	0 ms	240156 KB	Output is correct
9	Correct	0 ms	240156 KB	Output is correct
10	Correct	0 ms	240156 KB	Output is correct
11	Correct	0 ms	240156 KB	Output is correct
12	Correct	903 ms	240156 KB	Output is correct
13	Correct	543 ms	240156 KB	Output is correct
14	Correct	849 ms	240156 KB	Output is correct
15	Correct	1059 ms	240156 KB	Output is correct
16	Correct	706 ms	240156 KB	Output is correct
17	Correct	1076 ms	240156 KB	Output is correct
18	Correct	936 ms	240156 KB	Output is correct
19	Correct	1316 ms	240156 KB	Output is correct
20	Correct	2939 ms	240156 KB	Output is correct
21	Correct	409 ms	240156 KB	Output is correct
22	Correct	3399 ms	240156 KB	Output is correct
23	Correct	283 ms	240156 KB	Output is correct
24	Correct	1299 ms	240156 KB	Output is correct
25	Correct	2343 ms	240156 KB	Output is correct
26	Correct	2409 ms	240156 KB	Output is correct
27	Correct	2146 ms	240156 KB	Output is correct
28	Correct	1126 ms	240156 KB	Output is correct
29	Correct	3423 ms	240156 KB	Output is correct
30	Correct	8383 ms	240156 KB	Output is correct
31	Correct	7306 ms	240156 KB	Output is correct
32	Correct	786 ms	240156 KB	Output is correct
33	Correct	1059 ms	240156 KB	Output is correct
34	Correct	559 ms	240156 KB	Output is correct
35	Correct	2189 ms	240156 KB	Output is correct
36	Correct	4489 ms	240156 KB	Output is correct
37	Correct	3806 ms	240156 KB	Output is correct
38	Correct	3776 ms	240156 KB	Output is correct
39	Runtime error	1849 ms	240156 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-

Submission #29957

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
0 / 20.0