oj.uz

Submission #281938

# Submission time Handle Problem Language Result Execution time Memory
281938 2020-08-23T15:59:27 Z shayan_p Game (IOI13_game) C++14
100 / 100
 7684 ms 49392 KB 
// 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, x = 0;
    node *L = 0, *R = 0;
    int pos = 0, S = 0;
    node(int _pos, ll _g){
	pos = _pos, g = _g, x = _g;
	S = 1;
    }
    void rest(int _pos, ll _g){
	pos = _pos, g = _g, x = _g;
	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);
    }
	
};
 
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 ));    
}
pair<node*, node*> split(node* nw, int x){
    if(nw == 0)
	return {0, 0};
    if(nw->pos < x){
	auto it = split(nw->R, x);
	nw->R = it.F;
	build(nw);
	return {nw, it.S};
    }
    else{
	auto it = split(nw->L, x);
	nw->L = it.S;
	build(nw);
	return {it.F, nw};
    }
    assert(0);
}
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);
} 
pair<node*, ll> _ask(node *nw, int f, int s){
    assert(nw);
    auto A = split(nw, f);
    auto B = split(A.S, s);
    ll ans = (B.F ? B.F->g : 0);
    return {merge(A.F, merge(B.F, B.S)), ans};
}
node* _put(node *nw, int pos, ll x){
    //    assert(nw);
    auto A = split(nw, pos);
    auto B = split(A.S, pos+1);
    node* r = B.F;
    if(r == 0)
	r = new node(pos, x);
    else
	r->rest(pos, x);
    return merge(A.F, merge(r, B.S));
}
 
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){
	    if(!g)
		return 0;
	    auto it = _ask(g, ff, ss);
	    g = it.F;
	    return it.S;
	}
	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 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 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 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 0 ms 256 KB Output is correct
4 Correct 1452 ms 6524 KB Output is correct
5 Correct 553 ms 6800 KB Output is correct
6 Correct 1378 ms 3624 KB Output is correct
7 Correct 1649 ms 3444 KB Output is correct
8 Correct 1081 ms 3192 KB Output is correct
9 Correct 1535 ms 3504 KB Output is correct
10 Correct 1390 ms 2940 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 0 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 2197 ms 9848 KB Output is correct
13 Correct 4125 ms 6564 KB Output is correct
14 Correct 510 ms 4984 KB Output is correct
15 Correct 4560 ms 7612 KB Output is correct
16 Correct 361 ms 9332 KB Output is correct
17 Correct 2129 ms 8316 KB Output is correct
18 Correct 3733 ms 10284 KB Output is correct
19 Correct 3180 ms 10420 KB Output is correct
20 Correct 2892 ms 9832 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 1455 ms 6648 KB Output is correct
13 Correct 544 ms 6852 KB Output is correct
14 Correct 1395 ms 3552 KB Output is correct
15 Correct 1620 ms 3320 KB Output is correct
16 Correct 1042 ms 2996 KB Output is correct
17 Correct 1507 ms 3348 KB Output is correct
18 Correct 1402 ms 2984 KB Output is correct
19 Correct 2221 ms 9716 KB Output is correct
20 Correct 4132 ms 6392 KB Output is correct
21 Correct 516 ms 4600 KB Output is correct
22 Correct 4492 ms 7080 KB Output is correct
23 Correct 373 ms 8952 KB Output is correct
24 Correct 2125 ms 8036 KB Output is correct
25 Correct 3827 ms 10000 KB Output is correct
26 Correct 3249 ms 10108 KB Output is correct
27 Correct 2955 ms 10148 KB Output is correct
28 Correct 1265 ms 27380 KB Output is correct
29 Correct 3136 ms 30864 KB Output is correct
30 Correct 5465 ms 22480 KB Output is correct
31 Correct 4841 ms 18828 KB Output is correct
32 Correct 638 ms 7416 KB Output is correct
33 Correct 1022 ms 7800 KB Output is correct
34 Correct 569 ms 26488 KB Output is correct
35 Correct 2625 ms 18380 KB Output is correct
36 Correct 5151 ms 27768 KB Output is correct
37 Correct 4445 ms 28444 KB Output is correct
38 Correct 4096 ms 27884 KB Output is correct
39 Correct 3333 ms 23712 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 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 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 1444 ms 7124 KB Output is correct
13 Correct 557 ms 7416 KB Output is correct
14 Correct 1416 ms 4104 KB Output is correct
15 Correct 1602 ms 3832 KB Output is correct
16 Correct 1037 ms 3740 KB Output is correct
17 Correct 1500 ms 3948 KB Output is correct
18 Correct 1362 ms 3448 KB Output is correct
19 Correct 2167 ms 9544 KB Output is correct
20 Correct 4165 ms 6604 KB Output is correct
21 Correct 509 ms 4728 KB Output is correct
22 Correct 4491 ms 7608 KB Output is correct
23 Correct 379 ms 9200 KB Output is correct
24 Correct 2137 ms 7752 KB Output is correct
25 Correct 3689 ms 10052 KB Output is correct
26 Correct 3124 ms 10096 KB Output is correct
27 Correct 2993 ms 9396 KB Output is correct
28 Correct 1407 ms 26744 KB Output is correct
29 Correct 3172 ms 30968 KB Output is correct
30 Correct 5240 ms 22940 KB Output is correct
31 Correct 4751 ms 19348 KB Output is correct
32 Correct 633 ms 7764 KB Output is correct
33 Correct 1020 ms 7800 KB Output is correct
34 Correct 629 ms 27640 KB Output is correct
35 Correct 2549 ms 18168 KB Output is correct
36 Correct 5154 ms 27988 KB Output is correct
37 Correct 3809 ms 27948 KB Output is correct
38 Correct 4022 ms 27264 KB Output is correct
39 Correct 1768 ms 47660 KB Output is correct
40 Correct 4949 ms 49392 KB Output is correct
41 Correct 7684 ms 38368 KB Output is correct
42 Correct 6744 ms 29724 KB Output is correct
43 Correct 967 ms 47496 KB Output is correct
44 Correct 919 ms 4088 KB Output is correct
45 Correct 3227 ms 19848 KB Output is correct
46 Correct 6413 ms 47840 KB Output is correct
47 Correct 6514 ms 47860 KB Output is correct
48 Correct 6440 ms 47604 KB Output is correct
49 Correct 1 ms 256 KB Output is correct