Submission #281819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
281819	2020-08-23T14:07:05 Z	shayan_p	Game (IOI13_game)	C++14	63 / 100	2011 ms	256004 KB

game

// And you curse yourself for things you never done

#include<bits/stdc++.h>
#include "game.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int N, M;

struct node{
    ll g = 0;
    node *L = 0, *R = 0;
    void put(int pos, ll x, int l = 0, int r = M){
	if(r-l == 1){
	    g = x;
	    return;
	}
	int mid = (l+r) >> 1;
	if(pos < mid){
	    if(!L)
		L = new node();
	    L->put(pos, x, l, mid);
	}
	else{
	    if(!R)
		R = new node();
	    R->put(pos, x, mid, r);
	}
	g = __gcd(L ? L->g : 0, R ? R->g : 0);
    }
    ll ask(int f, int s, int l = 0, int r = M){
	if(r <= f || s <= l)
	    return 0;
	if(f <= l && r <= s)
	    return g;
	int mid = (l+r) >> 1;
	return __gcd(L ? L->ask(f, s, l, mid) : 0, R ? R->ask(f, s, mid, r) : 0);
    }
};
struct node2{
    node* g = 0;
    node2 *L = 0, *R = 0;
    void put(int posx, int posy, ll x, int l = 0, int r = N){
	ll num = x;
	if(r-l > 1){
	    int mid = (l+r) >> 1;
	    if(posx < mid){
		if(!L)
		    L = new node2();
		L->put(posx, posy, x, l, mid);
	    }
	    else{
		if(!R)
		    R = new node2();
		R->put(posx, posy, x, mid, r);
	    }
	    num = __gcd(L ? L->g->ask(posy, posy+1) : 0, R ? R->g->ask(posy, posy+1) : 0);
	}
	if(!g)
	    g = new node();
	g->put(posy, num);
    }
    ll ask(int f, int s, int ff, int ss, int l = 0, int r = N){
	if(r <= f || s <= l)
	    return 0;
	if(f <= l && r <= s)
	    return g ? g->ask(ff, ss) : 0;
	int mid = (l+r) >> 1;
	return __gcd(L ? L->ask(f, s, ff, ss, l, mid) : 0, R ? R->ask(f, s, ff, ss, mid, r) : 0);
    }
};

node2* root;

void init(int N, int M){
    ::N = N, ::M = M;
    root = new node2();
}
void update(int x, int y, ll w){
    root->put(x, y, w);
}
ll calculate(int x, int y, int xx, int yy){
    return root->ask(x, ++xx, y, ++yy);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	256 KB	Output is correct

Subtask #2
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	603 ms	13484 KB	Output is correct
5	Correct	453 ms	13796 KB	Output is correct
6	Correct	586 ms	10820 KB	Output is correct
7	Correct	626 ms	10496 KB	Output is correct
8	Correct	414 ms	7472 KB	Output is correct
9	Correct	649 ms	10420 KB	Output is correct
10	Correct	539 ms	10076 KB	Output is correct
11	Correct	1 ms	256 KB	Output is correct

Subtask #3
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	911 ms	17448 KB	Output is correct
13	Correct	1477 ms	8164 KB	Output is correct
14	Correct	318 ms	2808 KB	Output is correct
15	Correct	1756 ms	10616 KB	Output is correct
16	Correct	284 ms	20216 KB	Output is correct
17	Correct	988 ms	13304 KB	Output is correct
18	Correct	1636 ms	20592 KB	Output is correct
19	Correct	1451 ms	20496 KB	Output is correct
20	Correct	1353 ms	19988 KB	Output is correct
21	Correct	1 ms	256 KB	Output is correct

Subtask #4
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	1 ms	288 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	635 ms	13560 KB	Output is correct
13	Correct	439 ms	13772 KB	Output is correct
14	Correct	539 ms	10872 KB	Output is correct
15	Correct	610 ms	10488 KB	Output is correct
16	Correct	392 ms	7544 KB	Output is correct
17	Correct	566 ms	10492 KB	Output is correct
18	Correct	551 ms	9992 KB	Output is correct
19	Correct	968 ms	17400 KB	Output is correct
20	Correct	1435 ms	8184 KB	Output is correct
21	Correct	305 ms	2808 KB	Output is correct
22	Correct	1683 ms	10616 KB	Output is correct
23	Correct	295 ms	20088 KB	Output is correct
24	Correct	958 ms	13304 KB	Output is correct
25	Correct	1632 ms	20456 KB	Output is correct
26	Correct	1480 ms	20544 KB	Output is correct
27	Correct	1434 ms	20436 KB	Output is correct
28	Correct	1153 ms	253304 KB	Output is correct
29	Runtime error	2011 ms	256004 KB	Execution killed with signal 9
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	600 ms	13820 KB	Output is correct
13	Correct	428 ms	14200 KB	Output is correct
14	Correct	520 ms	11512 KB	Output is correct
15	Correct	602 ms	11000 KB	Output is correct
16	Correct	387 ms	8184 KB	Output is correct
17	Correct	582 ms	11128 KB	Output is correct
18	Correct	551 ms	10740 KB	Output is correct
19	Correct	928 ms	17600 KB	Output is correct
20	Correct	1458 ms	8116 KB	Output is correct
21	Correct	322 ms	2864 KB	Output is correct
22	Correct	1681 ms	10744 KB	Output is correct
23	Correct	267 ms	20216 KB	Output is correct
24	Correct	927 ms	13348 KB	Output is correct
25	Correct	1625 ms	20472 KB	Output is correct
26	Correct	1394 ms	20656 KB	Output is correct
27	Correct	1377 ms	19704 KB	Output is correct
28	Correct	1083 ms	253052 KB	Output is correct
29	Runtime error	1955 ms	256004 KB	Execution killed with signal 9
30	Halted	0 ms	0 KB	-

Submission #281819

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.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
26.0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0