답안 #281840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
281840	2020-08-23T14:31:00 Z	shayan_p	게임 (IOI13_game)	C++14	80 / 100	4119 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;

const int MAX = (3e5) * 70;

int N, M;

int L[MAX], R[MAX];
ll g[MAX];
int C;

inline int NEW(){
    return ++C;
}
void _put(int id, int pos, ll x, int l = 0, int r = M){
    if(r-l == 1){
	g[id] = x;
	return;
    }
    int mid = (l+r) >> 1;
    if(pos < mid){
	if(!L[id])
	    L[id] = NEW();
	_put(L[id], pos, x, l, mid);
    }
    else{
	if(!R[id])
	    R[id] = NEW();
	_put(R[id], pos, x, mid, r);
    }
    g[id] = __gcd(L[id] ? g[L[id]] : 0, R[id] ? g[R[id]] : 0);
}
ll _ask(int id, int f, int s, int l = 0, int r = M){
    if(r <= f || s <= l)
	return 0;
    if(f <= l && r <= s)
	return g[id];
    int mid = (l+r) >> 1;
    return __gcd(L[id] ? _ask(L[id], f, s, l, mid) : 0, R[id] ? _ask(R[id], f, s, mid, r) : 0);
}
struct node2{
    int 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 ? _ask(L->g, posy, posy+1) : 0, R ? _ask(R->g, posy, posy+1) : 0);
	}
	if(!g)
	    g = NEW();
	_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 ? _ask(g, 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

#	결과	실행 시간	메모리	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	384 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	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	1 ms	384 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	620 ms	8520 KB	Output is correct
5	Correct	463 ms	10744 KB	Output is correct
6	Correct	512 ms	7672 KB	Output is correct
7	Correct	652 ms	7416 KB	Output is correct
8	Correct	392 ms	6264 KB	Output is correct
9	Correct	542 ms	7416 KB	Output is correct
10	Correct	519 ms	7032 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	288 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	384 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	288 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	1010 ms	10488 KB	Output is correct
13	Correct	1558 ms	4600 KB	Output is correct
14	Correct	306 ms	1912 KB	Output is correct
15	Correct	1816 ms	6320 KB	Output is correct
16	Correct	249 ms	10872 KB	Output is correct
17	Correct	862 ms	7544 KB	Output is correct
18	Correct	1559 ms	11384 KB	Output is correct
19	Correct	1272 ms	11128 KB	Output is correct
20	Correct	1180 ms	10508 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	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	384 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	384 KB	Output is correct
8	Correct	0 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	600 ms	8760 KB	Output is correct
13	Correct	464 ms	11000 KB	Output is correct
14	Correct	506 ms	7920 KB	Output is correct
15	Correct	577 ms	7416 KB	Output is correct
16	Correct	391 ms	6264 KB	Output is correct
17	Correct	564 ms	7500 KB	Output is correct
18	Correct	540 ms	7032 KB	Output is correct
19	Correct	1032 ms	11896 KB	Output is correct
20	Correct	1587 ms	4792 KB	Output is correct
21	Correct	311 ms	2296 KB	Output is correct
22	Correct	1799 ms	6776 KB	Output is correct
23	Correct	246 ms	11128 KB	Output is correct
24	Correct	833 ms	8312 KB	Output is correct
25	Correct	1500 ms	11876 KB	Output is correct
26	Correct	1375 ms	12004 KB	Output is correct
27	Correct	1304 ms	11716 KB	Output is correct
28	Correct	833 ms	130808 KB	Output is correct
29	Correct	2222 ms	148508 KB	Output is correct
30	Correct	4119 ms	108336 KB	Output is correct
31	Correct	3882 ms	83848 KB	Output is correct
32	Correct	547 ms	5476 KB	Output is correct
33	Correct	757 ms	6832 KB	Output is correct
34	Correct	566 ms	145912 KB	Output is correct
35	Correct	1863 ms	76432 KB	Output is correct
36	Correct	3348 ms	145784 KB	Output is correct
37	Correct	2709 ms	146104 KB	Output is correct
38	Correct	2647 ms	145488 KB	Output is correct
39	Correct	2278 ms	113556 KB	Output is correct
40	Correct	1 ms	384 KB	Output is correct

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	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	384 KB	Output is correct
5	Correct	1 ms	384 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	607 ms	8952 KB	Output is correct
13	Correct	453 ms	10360 KB	Output is correct
14	Correct	534 ms	7460 KB	Output is correct
15	Correct	593 ms	7180 KB	Output is correct
16	Correct	395 ms	6076 KB	Output is correct
17	Correct	585 ms	7288 KB	Output is correct
18	Correct	571 ms	6904 KB	Output is correct
19	Correct	1018 ms	11768 KB	Output is correct
20	Correct	1555 ms	5168 KB	Output is correct
21	Correct	310 ms	2404 KB	Output is correct
22	Correct	1856 ms	6344 KB	Output is correct
23	Correct	243 ms	11260 KB	Output is correct
24	Correct	849 ms	8264 KB	Output is correct
25	Correct	1561 ms	11640 KB	Output is correct
26	Correct	1243 ms	11888 KB	Output is correct
27	Correct	1220 ms	11056 KB	Output is correct
28	Correct	919 ms	130424 KB	Output is correct
29	Correct	2226 ms	148356 KB	Output is correct
30	Correct	4069 ms	108032 KB	Output is correct
31	Correct	3794 ms	83592 KB	Output is correct
32	Correct	532 ms	4600 KB	Output is correct
33	Correct	722 ms	5368 KB	Output is correct
34	Correct	560 ms	144632 KB	Output is correct
35	Correct	1602 ms	75468 KB	Output is correct
36	Correct	3005 ms	144760 KB	Output is correct
37	Correct	2571 ms	145068 KB	Output is correct
38	Correct	2748 ms	144484 KB	Output is correct
39	Runtime error	1154 ms	256004 KB	Execution killed with signal 9
40	Halted	0 ms	0 KB	-