Submission #281987

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
281987	2020-08-23T18:27:02 Z	shayan_p	Game (IOI13_game)	C++14	100 / 100	3657 ms	60824 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;
 
const int inf = 1e9 + 10;
 
int N, M;
 
struct node{
    ll g = 0, x = 0;
    node *L = 0, *R = 0;
    int pos = 0, S = 0, MN, MX;
    node(int _pos, ll _g){
	pos = _pos, g = _g, x = _g, MN = MX = _pos;
	S = 1;
    }
    void rest(int _pos, ll _g){
	pos = _pos, g = _g, x = _g, MN = MX = _pos;
	S = 1;
    }
    ll ask(int _pos){
	if(pos == _pos)
	    return x;
	if(_pos < pos)
	    return (L ? L->ask(_pos) : 0);
	else
	    return (R ? R->ask(_pos) : 0);
    }
    ll ask(int f, int s){
	if(f <= MN && MX < s)
	    return g;
	if(s <= MN || MX < f)
	    return 0;
	ll ans = 0;
	if(f <= pos && pos < s)
	    ans = x;
	if(L)
	    ans = __gcd(ans, L->ask(f, s));
	if(R)
	    ans = __gcd(ans, R->ask(f, s));
	return ans;
    }
};
void build(node* nw){
    nw->S = (nw->L ? nw->L->S : 0) + (nw->R ? nw->R->S : 0) + 1;
    nw->g = __gcd(nw->x, __gcd( nw->L ? nw->L->g : 0, nw->R ? nw->R->g : 0 ));
    nw->MN = min({nw->pos, nw->L ? nw->L->MN : inf, nw->R ? nw->R->MN : inf});
    nw->MX = max({nw->pos, nw->L ? nw->L->MX : -inf, nw->R ? nw->R->MX : -inf});
}
void split(node* nw, int x, node *&L, node *&R){
    if(nw == 0){
	L = R = 0;
	return;
    }
    if(nw->pos < x){
	split(nw->R, x, L, R);
	nw->R = L;
	build(nw);
	L = nw;
    }
    else{
	split(nw->L, x, L, R);
	nw->L = R;
	build(nw);
	R = nw;
    }
}
node* merge(node *A, node *B){
    if(A == 0)
	return B;
    if(B == 0)
	return A;
    if((rand() % (A->S + B->S)) < A->S){
	A->R = merge(A->R, B);
	build(A);
	return A;
    }
    else{
	B->L = merge(A, B->L);
	build(B);
	return B;
    }
    assert(0);
} 
node* _put(node *nw, int pos, ll x){
    node *A, *B, *C;
    split(nw, pos, A, B);
    split(B, pos+1, B, C);
    if(B == 0)
	B = new node(pos, x);
    else
	B->rest(pos, x);
    return merge(A, merge(B, C));
}
 
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) : 0, R ? R->g->ask(posy) : 0);
	}
	if(!g)
	    g = new node(posy, num);
	else	    
	    g = _put(g, 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){
    srand(time(0));
    ::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	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	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	662 ms	7160 KB	Output is correct
5	Correct	342 ms	7876 KB	Output is correct
6	Correct	692 ms	4528 KB	Output is correct
7	Correct	804 ms	5240 KB	Output is correct
8	Correct	491 ms	4728 KB	Output is correct
9	Correct	740 ms	5388 KB	Output is correct
10	Correct	701 ms	4984 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	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	0 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	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	905 ms	9432 KB	Output is correct
13	Correct	1432 ms	3832 KB	Output is correct
14	Correct	323 ms	2424 KB	Output is correct
15	Correct	1523 ms	6008 KB	Output is correct
16	Correct	401 ms	8728 KB	Output is correct
17	Correct	941 ms	6392 KB	Output is correct
18	Correct	1826 ms	9056 KB	Output is correct
19	Correct	1488 ms	9080 KB	Output is correct
20	Correct	1376 ms	8440 KB	Output is correct
21	Correct	1 ms	256 KB	Output is correct

Subtask #4

17.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	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	685 ms	7032 KB	Output is correct
13	Correct	367 ms	7576 KB	Output is correct
14	Correct	654 ms	4088 KB	Output is correct
15	Correct	754 ms	5240 KB	Output is correct
16	Correct	457 ms	4728 KB	Output is correct
17	Correct	706 ms	5444 KB	Output is correct
18	Correct	677 ms	4984 KB	Output is correct
19	Correct	920 ms	11000 KB	Output is correct
20	Correct	1418 ms	5616 KB	Output is correct
21	Correct	317 ms	2808 KB	Output is correct
22	Correct	1487 ms	6520 KB	Output is correct
23	Correct	344 ms	9080 KB	Output is correct
24	Correct	885 ms	6756 KB	Output is correct
25	Correct	1753 ms	9348 KB	Output is correct
26	Correct	1378 ms	9336 KB	Output is correct
27	Correct	1294 ms	8568 KB	Output is correct
28	Correct	568 ms	28412 KB	Output is correct
29	Correct	1512 ms	31352 KB	Output is correct
30	Correct	1862 ms	23416 KB	Output is correct
31	Correct	1722 ms	18444 KB	Output is correct
32	Correct	462 ms	2888 KB	Output is correct
33	Correct	599 ms	3448 KB	Output is correct
34	Correct	439 ms	27768 KB	Output is correct
35	Correct	1180 ms	16332 KB	Output is correct
36	Correct	2475 ms	28932 KB	Output is correct
37	Correct	2061 ms	29144 KB	Output is correct
38	Correct	1979 ms	28208 KB	Output is correct
39	Correct	1748 ms	22996 KB	Output is correct
40	Correct	1 ms	256 KB	Output is correct

Subtask #5

20.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	0 ms	256 KB	Output is correct
8	Correct	1 ms	384 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	689 ms	7672 KB	Output is correct
13	Correct	383 ms	7884 KB	Output is correct
14	Correct	753 ms	4628 KB	Output is correct
15	Correct	795 ms	6264 KB	Output is correct
16	Correct	487 ms	5752 KB	Output is correct
17	Correct	743 ms	6392 KB	Output is correct
18	Correct	700 ms	6008 KB	Output is correct
19	Correct	978 ms	11256 KB	Output is correct
20	Correct	1460 ms	5880 KB	Output is correct
21	Correct	325 ms	3120 KB	Output is correct
22	Correct	1544 ms	6776 KB	Output is correct
23	Correct	337 ms	9336 KB	Output is correct
24	Correct	925 ms	7160 KB	Output is correct
25	Correct	1850 ms	9744 KB	Output is correct
26	Correct	1462 ms	9808 KB	Output is correct
27	Correct	1440 ms	9236 KB	Output is correct
28	Correct	586 ms	28308 KB	Output is correct
29	Correct	1609 ms	31440 KB	Output is correct
30	Correct	1966 ms	23212 KB	Output is correct
31	Correct	1712 ms	18232 KB	Output is correct
32	Correct	459 ms	3064 KB	Output is correct
33	Correct	674 ms	3800 KB	Output is correct
34	Correct	458 ms	27352 KB	Output is correct
35	Correct	1211 ms	16456 KB	Output is correct
36	Correct	2619 ms	28972 KB	Output is correct
37	Correct	2025 ms	28984 KB	Output is correct
38	Correct	2116 ms	28216 KB	Output is correct
39	Correct	891 ms	58384 KB	Output is correct
40	Correct	2877 ms	60824 KB	Output is correct
41	Correct	3092 ms	47652 KB	Output is correct
42	Correct	2848 ms	36780 KB	Output is correct
43	Correct	997 ms	58088 KB	Output is correct
44	Correct	725 ms	4672 KB	Output is correct
45	Correct	1639 ms	24344 KB	Output is correct
46	Correct	3573 ms	59060 KB	Output is correct
47	Correct	3657 ms	58968 KB	Output is correct
48	Correct	3457 ms	58616 KB	Output is correct
49	Correct	1 ms	256 KB	Output is correct