Submission #281988

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
281988	2020-08-23T18:28:03 Z	shayan_p	Game (IOI13_game)	C++14	100 / 100	3572 ms	57080 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);
} 
void _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);
    nw = 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	    
	    _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	0 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	2 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	0 ms	256 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	0 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	693 ms	7032 KB	Output is correct
5	Correct	372 ms	7332 KB	Output is correct
6	Correct	680 ms	4060 KB	Output is correct
7	Correct	763 ms	3796 KB	Output is correct
8	Correct	469 ms	3292 KB	Output is correct
9	Correct	769 ms	3976 KB	Output is correct
10	Correct	719 ms	3576 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	2 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	384 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	941 ms	9444 KB	Output is correct
13	Correct	1459 ms	3704 KB	Output is correct
14	Correct	327 ms	1020 KB	Output is correct
15	Correct	1578 ms	4676 KB	Output is correct
16	Correct	371 ms	7160 KB	Output is correct
17	Correct	896 ms	5008 KB	Output is correct
18	Correct	1821 ms	7452 KB	Output is correct
19	Correct	1459 ms	7656 KB	Output is correct
20	Correct	1444 ms	7296 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	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	665 ms	7160 KB	Output is correct
13	Correct	333 ms	7288 KB	Output is correct
14	Correct	691 ms	4360 KB	Output is correct
15	Correct	773 ms	3796 KB	Output is correct
16	Correct	464 ms	3320 KB	Output is correct
17	Correct	742 ms	3916 KB	Output is correct
18	Correct	763 ms	3576 KB	Output is correct
19	Correct	972 ms	9208 KB	Output is correct
20	Correct	1448 ms	3788 KB	Output is correct
21	Correct	315 ms	888 KB	Output is correct
22	Correct	1546 ms	4588 KB	Output is correct
23	Correct	338 ms	7164 KB	Output is correct
24	Correct	929 ms	4856 KB	Output is correct
25	Correct	1981 ms	7832 KB	Output is correct
26	Correct	1531 ms	8056 KB	Output is correct
27	Correct	1484 ms	7416 KB	Output is correct
28	Correct	616 ms	26492 KB	Output is correct
29	Correct	1538 ms	29560 KB	Output is correct
30	Correct	1954 ms	21904 KB	Output is correct
31	Correct	1766 ms	16924 KB	Output is correct
32	Correct	465 ms	1400 KB	Output is correct
33	Correct	620 ms	1924 KB	Output is correct
34	Correct	448 ms	26488 KB	Output is correct
35	Correct	1334 ms	14556 KB	Output is correct
36	Correct	2418 ms	26872 KB	Output is correct
37	Correct	2043 ms	27248 KB	Output is correct
38	Correct	2106 ms	26560 KB	Output is correct
39	Correct	1515 ms	21488 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	2 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	675 ms	7076 KB	Output is correct
13	Correct	350 ms	7416 KB	Output is correct
14	Correct	653 ms	4216 KB	Output is correct
15	Correct	750 ms	3832 KB	Output is correct
16	Correct	468 ms	3320 KB	Output is correct
17	Correct	742 ms	3960 KB	Output is correct
18	Correct	725 ms	3576 KB	Output is correct
19	Correct	950 ms	9208 KB	Output is correct
20	Correct	1390 ms	3832 KB	Output is correct
21	Correct	318 ms	1016 KB	Output is correct
22	Correct	1525 ms	4984 KB	Output is correct
23	Correct	334 ms	7288 KB	Output is correct
24	Correct	892 ms	4860 KB	Output is correct
25	Correct	1879 ms	7556 KB	Output is correct
26	Correct	1495 ms	7696 KB	Output is correct
27	Correct	1335 ms	7092 KB	Output is correct
28	Correct	568 ms	25848 KB	Output is correct
29	Correct	1636 ms	28960 KB	Output is correct
30	Correct	1844 ms	21308 KB	Output is correct
31	Correct	1718 ms	16504 KB	Output is correct
32	Correct	491 ms	1192 KB	Output is correct
33	Correct	651 ms	1440 KB	Output is correct
34	Correct	449 ms	25968 KB	Output is correct
35	Correct	1160 ms	14072 KB	Output is correct
36	Correct	2473 ms	26268 KB	Output is correct
37	Correct	2065 ms	26412 KB	Output is correct
38	Correct	2103 ms	25976 KB	Output is correct
39	Correct	787 ms	54904 KB	Output is correct
40	Correct	2818 ms	57080 KB	Output is correct
41	Correct	3058 ms	44792 KB	Output is correct
42	Correct	2878 ms	33944 KB	Output is correct
43	Correct	923 ms	55120 KB	Output is correct
44	Correct	765 ms	1144 KB	Output is correct
45	Correct	1620 ms	20728 KB	Output is correct
46	Correct	3524 ms	55376 KB	Output is correct
47	Correct	3572 ms	55460 KB	Output is correct
48	Correct	3547 ms	54872 KB	Output is correct
49	Correct	1 ms	256 KB	Output is correct