Submission #29942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
29942	2017-07-21T11:15:13 Z	osmanorhan	Game (IOI13_game)	C++14	37 / 100	3669 ms	160780 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 = 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[maxn*32], tr[maxn*32]; // 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	Memory	Grader output
1	Correct	160780 KB	Output is correct
2	Correct	160780 KB	Output is correct
3	Correct	160780 KB	Output is correct
4	Correct	160780 KB	Output is correct
5	Correct	160780 KB	Output is correct
6	Correct	160780 KB	Output is correct
7	Correct	160780 KB	Output is correct
8	Correct	160780 KB	Output is correct
9	Correct	160780 KB	Output is correct
10	Correct	160780 KB	Output is correct
11	Correct	160780 KB	Output is correct
12	Correct	160780 KB	Output is correct

Subtask #2
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	160780 KB	Output is correct
2	Correct	0 ms	160780 KB	Output is correct
3	Correct	0 ms	160780 KB	Output is correct
4	Correct	796 ms	160780 KB	Output is correct
5	Correct	603 ms	160780 KB	Output is correct
6	Correct	913 ms	160780 KB	Output is correct
7	Correct	789 ms	160780 KB	Output is correct
8	Correct	536 ms	160780 KB	Output is correct
9	Correct	1073 ms	160780 KB	Output is correct
10	Correct	739 ms	160780 KB	Output is correct
11	Correct	0 ms	160780 KB	Output is correct

Subtask #3
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	160780 KB	Output is correct
2	Correct	0 ms	160780 KB	Output is correct
3	Correct	0 ms	160780 KB	Output is correct
4	Correct	0 ms	160780 KB	Output is correct
5	Correct	0 ms	160780 KB	Output is correct
6	Correct	0 ms	160780 KB	Output is correct
7	Correct	0 ms	160780 KB	Output is correct
8	Correct	0 ms	160780 KB	Output is correct
9	Correct	0 ms	160780 KB	Output is correct
10	Correct	0 ms	160780 KB	Output is correct
11	Correct	0 ms	160780 KB	Output is correct
12	Correct	1263 ms	160780 KB	Output is correct
13	Correct	3159 ms	160780 KB	Output is correct
14	Correct	476 ms	160780 KB	Output is correct
15	Correct	3669 ms	160780 KB	Output is correct
16	Correct	239 ms	160780 KB	Output is correct
17	Correct	1526 ms	160780 KB	Output is correct
18	Incorrect	2826 ms	160780 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #4
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	160780 KB	Output is correct
2	Correct	0 ms	160780 KB	Output is correct
3	Correct	0 ms	160780 KB	Output is correct
4	Correct	0 ms	160780 KB	Output is correct
5	Correct	0 ms	160780 KB	Output is correct
6	Correct	0 ms	160780 KB	Output is correct
7	Correct	0 ms	160780 KB	Output is correct
8	Correct	0 ms	160780 KB	Output is correct
9	Correct	0 ms	160780 KB	Output is correct
10	Correct	0 ms	160780 KB	Output is correct
11	Correct	0 ms	160780 KB	Output is correct
12	Correct	903 ms	160780 KB	Output is correct
13	Correct	563 ms	160780 KB	Output is correct
14	Correct	833 ms	160780 KB	Output is correct
15	Correct	1002 ms	160780 KB	Output is correct
16	Correct	646 ms	160780 KB	Output is correct
17	Correct	1069 ms	160780 KB	Output is correct
18	Correct	843 ms	160780 KB	Output is correct
19	Correct	1346 ms	160780 KB	Output is correct
20	Correct	3093 ms	160780 KB	Output is correct
21	Correct	479 ms	160780 KB	Output is correct
22	Correct	3563 ms	160780 KB	Output is correct
23	Correct	286 ms	160780 KB	Output is correct
24	Correct	1619 ms	160780 KB	Output is correct
25	Incorrect	2846 ms	160780 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	160780 KB	Output is correct
2	Correct	0 ms	160780 KB	Output is correct
3	Correct	0 ms	160780 KB	Output is correct
4	Correct	0 ms	160780 KB	Output is correct
5	Correct	0 ms	160780 KB	Output is correct
6	Correct	0 ms	160780 KB	Output is correct
7	Correct	0 ms	160780 KB	Output is correct
8	Correct	0 ms	160780 KB	Output is correct
9	Correct	0 ms	160780 KB	Output is correct
10	Correct	0 ms	160780 KB	Output is correct
11	Correct	0 ms	160780 KB	Output is correct
12	Correct	926 ms	160780 KB	Output is correct
13	Correct	559 ms	160780 KB	Output is correct
14	Correct	849 ms	160780 KB	Output is correct
15	Correct	1056 ms	160780 KB	Output is correct
16	Correct	633 ms	160780 KB	Output is correct
17	Correct	986 ms	160780 KB	Output is correct
18	Correct	976 ms	160780 KB	Output is correct
19	Correct	1379 ms	160780 KB	Output is correct
20	Correct	3259 ms	160780 KB	Output is correct
21	Correct	483 ms	160780 KB	Output is correct
22	Correct	3606 ms	160780 KB	Output is correct
23	Correct	343 ms	160780 KB	Output is correct
24	Correct	1723 ms	160780 KB	Output is correct
25	Incorrect	2896 ms	160780 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Submission #29942

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0