답안 #43147 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43147	2018-03-09T14:07:23 Z	yusufake	게임 (IOI13_game)	C++	80 / 100	10276 ms	256000 KB

game

#include<bits/stdc++.h>
#include "game.h"
 
using namespace std;
 
#define _   int v, int tl, int tr
#define tm  (tl+tr >> 1)
#define sol L[v],tl,tm
#define sag R[v],tm+1,tr
 
#define mp make_pair
#define pb push_back
#define st first
#define nd second
 
typedef long long ll;
typedef pair < int , int > pp;
 
const int mod = 1e9 + 7;
const int N   = 22000 * 525;
 
int Y[N],L[N],R[N],posx,posy,lx,ly,rx,ry,id=1;
ll s[N],tt;
 
inline ll gcd(ll u, ll v) {
    ll r;
    while ( v != 0) { r = u % v; u = v; v = r; }
    return u;
}
 
inline ll qry_y(_) { 
	if(ly > tr || ry < tl || !v) return 0;
	if (ly <= tl && tr <= ry) return s[v];
	return gcd(qry_y(sol) , qry_y(sag));
}
inline ll qry_x(_) { 
	if(lx > tr || rx < tl) return 0;
	if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod);
	return gcd(qry_x(sol) , qry_x(sag));
}
 
void up_y(_, int r1, int r2, bool h){  // s[0] should contain ineffective element
	if(tl == tr){
		s[v] = h ? tt : gcd(s[r1] , s[r2]);
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,L[r1],L[r2],h); }
	s[v] = gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_){
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag); }
		else          { if(!L[v]) L[v] = ++id; up_x(sol); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,Y[ L[v] ],Y[ R[v] ],(tl==tr));
}
 
void update(int x, int y, ll t){
	posx = x;
	posy = y;
	tt = t;
	up_x(1,0,mod);
}	
ll calculate(int a, int b, int a2, int b2){
	lx = a; ly = b;
	rx = a2; ry = b2;
	return qry_x(1,0,mod);
}	
 
void init(int a, int b) {}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^
game.cpp: In function 'll qry_y(int, int, int)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^
game.cpp:34:19: note: in expansion of macro 'sol'
  return gcd(qry_y(sol) , qry_y(sag));
                   ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^
game.cpp:34:32: note: in expansion of macro 'sag'
  return gcd(qry_y(sol) , qry_y(sag));
                                ^
game.cpp: In function 'll qry_x(int, int, int)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^
game.cpp:39:19: note: in expansion of macro 'sol'
  return gcd(qry_x(sol) , qry_x(sag));
                   ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^
game.cpp:39:32: note: in expansion of macro 'sag'
  return gcd(qry_x(sol) , qry_x(sag));
                                ^
game.cpp: In function 'void up_y(int, int, int, int, int, bool)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:47:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
            ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^
game.cpp:47:46: note: in expansion of macro 'sag'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
                                              ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^
game.cpp:48:46: note: in expansion of macro 'sol'
  else          { if(!L[v]) L[v] = ++id; up_y(sol,L[r1],L[r2],h); }
                                              ^
game.cpp: In function 'void up_x(int, int, int)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:53:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag); }
             ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^
game.cpp:53:47: note: in expansion of macro 'sag'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag); }
                                               ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^
game.cpp:54:47: note: in expansion of macro 'sol'
   else          { if(!L[v]) L[v] = ++id; up_x(sol); }
                                               ^

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	612 KB	Output is correct
3	Correct	4 ms	720 KB	Output is correct
4	Correct	1 ms	720 KB	Output is correct
5	Correct	1 ms	720 KB	Output is correct
6	Correct	4 ms	856 KB	Output is correct
7	Correct	2 ms	856 KB	Output is correct
8	Correct	1 ms	856 KB	Output is correct
9	Correct	3 ms	856 KB	Output is correct
10	Correct	2 ms	856 KB	Output is correct
11	Correct	3 ms	856 KB	Output is correct
12	Correct	1 ms	856 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	856 KB	Output is correct
2	Correct	2 ms	856 KB	Output is correct
3	Correct	2 ms	856 KB	Output is correct
4	Correct	1101 ms	32388 KB	Output is correct
5	Correct	818 ms	36368 KB	Output is correct
6	Correct	1318 ms	38068 KB	Output is correct
7	Correct	1382 ms	42508 KB	Output is correct
8	Correct	912 ms	42508 KB	Output is correct
9	Correct	1305 ms	51612 KB	Output is correct
10	Correct	1195 ms	55740 KB	Output is correct
11	Correct	2 ms	55740 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	55740 KB	Output is correct
2	Correct	4 ms	55740 KB	Output is correct
3	Correct	5 ms	55740 KB	Output is correct
4	Correct	2 ms	55740 KB	Output is correct
5	Correct	2 ms	55740 KB	Output is correct
6	Correct	4 ms	55740 KB	Output is correct
7	Correct	2 ms	55740 KB	Output is correct
8	Correct	1 ms	55740 KB	Output is correct
9	Correct	3 ms	55740 KB	Output is correct
10	Correct	2 ms	55740 KB	Output is correct
11	Correct	3 ms	55740 KB	Output is correct
12	Correct	1491 ms	55740 KB	Output is correct
13	Correct	2477 ms	55740 KB	Output is correct
14	Correct	594 ms	55740 KB	Output is correct
15	Correct	2700 ms	57796 KB	Output is correct
16	Correct	589 ms	67720 KB	Output is correct
17	Correct	1597 ms	68680 KB	Output is correct
18	Correct	2530 ms	77984 KB	Output is correct
19	Correct	2437 ms	83564 KB	Output is correct
20	Correct	2324 ms	88344 KB	Output is correct
21	Correct	2 ms	88344 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	88344 KB	Output is correct
2	Correct	5 ms	88344 KB	Output is correct
3	Correct	4 ms	88344 KB	Output is correct
4	Correct	2 ms	88344 KB	Output is correct
5	Correct	1 ms	88344 KB	Output is correct
6	Correct	3 ms	88344 KB	Output is correct
7	Correct	2 ms	88344 KB	Output is correct
8	Correct	2 ms	88344 KB	Output is correct
9	Correct	3 ms	88344 KB	Output is correct
10	Correct	3 ms	88344 KB	Output is correct
11	Correct	3 ms	88344 KB	Output is correct
12	Correct	1130 ms	105724 KB	Output is correct
13	Correct	814 ms	110028 KB	Output is correct
14	Correct	1402 ms	111580 KB	Output is correct
15	Correct	1461 ms	115980 KB	Output is correct
16	Correct	921 ms	115980 KB	Output is correct
17	Correct	1415 ms	125120 KB	Output is correct
18	Correct	1296 ms	129116 KB	Output is correct
19	Correct	1532 ms	129116 KB	Output is correct
20	Correct	2459 ms	129116 KB	Output is correct
21	Correct	597 ms	129116 KB	Output is correct
22	Correct	2837 ms	131284 KB	Output is correct
23	Correct	615 ms	141064 KB	Output is correct
24	Correct	1685 ms	142232 KB	Output is correct
25	Correct	2704 ms	151612 KB	Output is correct
26	Correct	2506 ms	157064 KB	Output is correct
27	Correct	2282 ms	161856 KB	Output is correct
28	Correct	1235 ms	256000 KB	Output is correct
29	Correct	2915 ms	256000 KB	Output is correct
30	Correct	7274 ms	256000 KB	Output is correct
31	Correct	6745 ms	256000 KB	Output is correct
32	Correct	715 ms	256000 KB	Output is correct
33	Correct	1036 ms	256000 KB	Output is correct
34	Correct	1779 ms	256000 KB	Output is correct
35	Correct	2147 ms	256000 KB	Output is correct
36	Correct	4034 ms	256000 KB	Output is correct
37	Correct	3274 ms	256000 KB	Output is correct
38	Correct	3319 ms	256000 KB	Output is correct
39	Correct	3027 ms	256000 KB	Output is correct
40	Correct	2 ms	256000 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256000 KB	Output is correct
2	Correct	4 ms	256000 KB	Output is correct
3	Correct	4 ms	256000 KB	Output is correct
4	Correct	2 ms	256000 KB	Output is correct
5	Correct	2 ms	256000 KB	Output is correct
6	Correct	4 ms	256000 KB	Output is correct
7	Correct	2 ms	256000 KB	Output is correct
8	Correct	2 ms	256000 KB	Output is correct
9	Correct	3 ms	256000 KB	Output is correct
10	Correct	2 ms	256000 KB	Output is correct
11	Correct	2 ms	256000 KB	Output is correct
12	Correct	1126 ms	256000 KB	Output is correct
13	Correct	821 ms	256000 KB	Output is correct
14	Correct	1318 ms	256000 KB	Output is correct
15	Correct	1353 ms	256000 KB	Output is correct
16	Correct	852 ms	256000 KB	Output is correct
17	Correct	1351 ms	256000 KB	Output is correct
18	Correct	1233 ms	256000 KB	Output is correct
19	Correct	1554 ms	256000 KB	Output is correct
20	Correct	2452 ms	256000 KB	Output is correct
21	Correct	595 ms	256000 KB	Output is correct
22	Correct	2793 ms	256000 KB	Output is correct
23	Correct	609 ms	256000 KB	Output is correct
24	Correct	1709 ms	256000 KB	Output is correct
25	Correct	2775 ms	256000 KB	Output is correct
26	Correct	2449 ms	256000 KB	Output is correct
27	Correct	2218 ms	256000 KB	Output is correct
28	Correct	1186 ms	256000 KB	Output is correct
29	Correct	2869 ms	256000 KB	Output is correct
30	Correct	7125 ms	256000 KB	Output is correct
31	Correct	6637 ms	256000 KB	Output is correct
32	Correct	684 ms	256000 KB	Output is correct
33	Correct	965 ms	256000 KB	Output is correct
34	Correct	1677 ms	256000 KB	Output is correct
35	Correct	2118 ms	256000 KB	Output is correct
36	Correct	3982 ms	256000 KB	Output is correct
37	Correct	3606 ms	256000 KB	Output is correct
38	Correct	3388 ms	256000 KB	Output is correct
39	Execution timed out	10276 ms	256000 KB	Time limit exceeded (wall clock)
40	Halted	0 ms	0 KB	-

답안 #43147

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.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
17.0 / 17.0

Subtask #5
0 / 20.0