Submission #29965

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
29965	2017-07-21T11:30:29 Z	osmanorhan	Game (IOI13_game)	C++14	80 / 100	8983 ms	244656 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 = 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( 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	244656 KB	Output is correct
2	Correct	244656 KB	Output is correct
3	Correct	244656 KB	Output is correct
4	Correct	244656 KB	Output is correct
5	Correct	244656 KB	Output is correct
6	Correct	244656 KB	Output is correct
7	Correct	244656 KB	Output is correct
8	Correct	244656 KB	Output is correct
9	Correct	244656 KB	Output is correct
10	Correct	244656 KB	Output is correct
11	Correct	244656 KB	Output is correct
12	Correct	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	843 ms	244656 KB	Output is correct
5	Correct	573 ms	244656 KB	Output is correct
6	Correct	773 ms	244656 KB	Output is correct
7	Correct	1113 ms	244656 KB	Output is correct
8	Correct	629 ms	244656 KB	Output is correct
9	Correct	1053 ms	244656 KB	Output is correct
10	Correct	976 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	1293 ms	244656 KB	Output is correct
13	Correct	2986 ms	244656 KB	Output is correct
14	Correct	486 ms	244656 KB	Output is correct
15	Correct	3533 ms	244656 KB	Output is correct
16	Correct	309 ms	244656 KB	Output is correct
17	Correct	1503 ms	244656 KB	Output is correct
18	Correct	2433 ms	244656 KB	Output is correct
19	Correct	2116 ms	244656 KB	Output is correct
20	Correct	1993 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	879 ms	244656 KB	Output is correct
13	Correct	543 ms	244656 KB	Output is correct
14	Correct	926 ms	244656 KB	Output is correct
15	Correct	1076 ms	244656 KB	Output is correct
16	Correct	636 ms	244656 KB	Output is correct
17	Correct	996 ms	244656 KB	Output is correct
18	Correct	859 ms	244656 KB	Output is correct
19	Correct	1313 ms	244656 KB	Output is correct
20	Correct	3026 ms	244656 KB	Output is correct
21	Correct	439 ms	244656 KB	Output is correct
22	Correct	3556 ms	244656 KB	Output is correct
23	Correct	286 ms	244656 KB	Output is correct
24	Correct	1656 ms	244656 KB	Output is correct
25	Correct	2506 ms	244656 KB	Output is correct
26	Correct	2479 ms	244656 KB	Output is correct
27	Correct	1706 ms	244656 KB	Output is correct
28	Correct	1329 ms	244656 KB	Output is correct
29	Correct	3669 ms	244656 KB	Output is correct
30	Correct	8313 ms	244656 KB	Output is correct
31	Correct	7969 ms	244656 KB	Output is correct
32	Correct	943 ms	244656 KB	Output is correct
33	Correct	1239 ms	244656 KB	Output is correct
34	Correct	643 ms	244656 KB	Output is correct
35	Correct	2769 ms	244656 KB	Output is correct
36	Correct	4536 ms	244656 KB	Output is correct
37	Correct	4569 ms	244656 KB	Output is correct
38	Correct	4359 ms	244656 KB	Output is correct
39	Correct	3373 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	816 ms	244656 KB	Output is correct
13	Correct	476 ms	244656 KB	Output is correct
14	Correct	1006 ms	244656 KB	Output is correct
15	Correct	1073 ms	244656 KB	Output is correct
16	Correct	676 ms	244656 KB	Output is correct
17	Correct	959 ms	244656 KB	Output is correct
18	Correct	916 ms	244656 KB	Output is correct
19	Correct	1423 ms	244656 KB	Output is correct
20	Correct	3019 ms	244656 KB	Output is correct
21	Correct	436 ms	244656 KB	Output is correct
22	Correct	3659 ms	244656 KB	Output is correct
23	Correct	299 ms	244656 KB	Output is correct
24	Correct	1659 ms	244656 KB	Output is correct
25	Correct	2629 ms	244656 KB	Output is correct
26	Correct	2479 ms	244656 KB	Output is correct
27	Correct	2249 ms	244656 KB	Output is correct
28	Correct	979 ms	244656 KB	Output is correct
29	Correct	3439 ms	244656 KB	Output is correct
30	Correct	8983 ms	244656 KB	Output is correct
31	Correct	8193 ms	244656 KB	Output is correct
32	Correct	839 ms	244656 KB	Output is correct
33	Correct	1283 ms	244656 KB	Output is correct
34	Correct	739 ms	244656 KB	Output is correct
35	Correct	2839 ms	244656 KB	Output is correct
36	Correct	5306 ms	244656 KB	Output is correct
37	Correct	4283 ms	244656 KB	Output is correct
38	Correct	3716 ms	244656 KB	Output is correct
39	Runtime error	1326 ms	244656 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-

Submission #29965

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