답안 #43172 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43172	2018-03-09T17:45:59 Z	yusufake	게임 (IOI13_game)	C++	80 / 100	9280 ms	256000 KB

game

#include<stddef.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
  
typedef long long ll;
 
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){  // s[0] should contain ineffective element
	if(tl == tr){
		s[v] = r1 || r2 ? gcd(s[r1] , s[r2]) : tt;
		return;
	}
    int &l = L[v];
    int &r = R[v];
	if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
	else          { if(!l) l = ++id; up_y(l,tl,tm,L[r1],L[r2]); }
	s[v] = gcd(s[l] , s[r]);
}
void up_x(_){
    int &l = L[v];
    int &r = R[v];
	if(tl < tr){
		if(posx > tm) { if(!r) r = ++id; up_x(r,tm+1,tr); }
		else          { if(!l) l = ++id; up_x(l,tl,tm); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,Y[l],Y[r]);
}
 
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:28: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:28: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:33: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:33: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)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:43:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
            ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:43:42: note: in expansion of macro 'tm'
  if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
                                          ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:44:45: note: in expansion of macro 'tm'
  else          { if(!l) l = ++id; up_y(l,tl,tm,L[r1],L[r2]); }
                                             ^
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:51:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!r) r = ++id; up_x(r,tm+1,tr); }
             ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:51:43: note: in expansion of macro 'tm'
   if(posx > tm) { if(!r) r = ++id; up_x(r,tm+1,tr); }
                                           ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:52:46: note: in expansion of macro 'tm'
   else          { if(!l) l = ++id; up_x(l,tl,tm); }
                                              ^

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	812 KB	Output is correct
2	Correct	2 ms	812 KB	Output is correct
3	Correct	2 ms	812 KB	Output is correct
4	Correct	1117 ms	32124 KB	Output is correct
5	Correct	805 ms	36140 KB	Output is correct
6	Correct	1260 ms	37936 KB	Output is correct
7	Correct	1306 ms	42188 KB	Output is correct
8	Correct	812 ms	42188 KB	Output is correct
9	Correct	1373 ms	51360 KB	Output is correct
10	Correct	1156 ms	55440 KB	Output is correct
11	Correct	2 ms	55440 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	55440 KB	Output is correct
2	Correct	4 ms	55440 KB	Output is correct
3	Correct	4 ms	55440 KB	Output is correct
4	Correct	1 ms	55440 KB	Output is correct
5	Correct	1 ms	55440 KB	Output is correct
6	Correct	4 ms	55440 KB	Output is correct
7	Correct	2 ms	55440 KB	Output is correct
8	Correct	2 ms	55440 KB	Output is correct
9	Correct	3 ms	55440 KB	Output is correct
10	Correct	2 ms	55440 KB	Output is correct
11	Correct	2 ms	55440 KB	Output is correct
12	Correct	1490 ms	55440 KB	Output is correct
13	Correct	2418 ms	55440 KB	Output is correct
14	Correct	580 ms	55440 KB	Output is correct
15	Correct	2763 ms	57552 KB	Output is correct
16	Correct	646 ms	67424 KB	Output is correct
17	Correct	1678 ms	68528 KB	Output is correct
18	Correct	2716 ms	77964 KB	Output is correct
19	Correct	2348 ms	83352 KB	Output is correct
20	Correct	2099 ms	88008 KB	Output is correct
21	Correct	2 ms	88008 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	88008 KB	Output is correct
2	Correct	3 ms	88008 KB	Output is correct
3	Correct	3 ms	88008 KB	Output is correct
4	Correct	1 ms	88008 KB	Output is correct
5	Correct	1 ms	88008 KB	Output is correct
6	Correct	3 ms	88008 KB	Output is correct
7	Correct	1 ms	88008 KB	Output is correct
8	Correct	1 ms	88008 KB	Output is correct
9	Correct	3 ms	88008 KB	Output is correct
10	Correct	2 ms	88008 KB	Output is correct
11	Correct	2 ms	88008 KB	Output is correct
12	Correct	1034 ms	105480 KB	Output is correct
13	Correct	790 ms	109552 KB	Output is correct
14	Correct	1286 ms	111400 KB	Output is correct
15	Correct	1306 ms	115552 KB	Output is correct
16	Correct	773 ms	115552 KB	Output is correct
17	Correct	1315 ms	124568 KB	Output is correct
18	Correct	1100 ms	128880 KB	Output is correct
19	Correct	1447 ms	128880 KB	Output is correct
20	Correct	2396 ms	128880 KB	Output is correct
21	Correct	589 ms	128880 KB	Output is correct
22	Correct	2752 ms	131020 KB	Output is correct
23	Correct	552 ms	140716 KB	Output is correct
24	Correct	1547 ms	141780 KB	Output is correct
25	Correct	2477 ms	151292 KB	Output is correct
26	Correct	2222 ms	156700 KB	Output is correct
27	Correct	2097 ms	161336 KB	Output is correct
28	Correct	1142 ms	256000 KB	Output is correct
29	Correct	2749 ms	256000 KB	Output is correct
30	Correct	7020 ms	256000 KB	Output is correct
31	Correct	6287 ms	256000 KB	Output is correct
32	Correct	714 ms	256000 KB	Output is correct
33	Correct	938 ms	256000 KB	Output is correct
34	Correct	1741 ms	256000 KB	Output is correct
35	Correct	2047 ms	256000 KB	Output is correct
36	Correct	3661 ms	256000 KB	Output is correct
37	Correct	3102 ms	256000 KB	Output is correct
38	Correct	3107 ms	256000 KB	Output is correct
39	Correct	2779 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	1 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	1098 ms	256000 KB	Output is correct
13	Correct	836 ms	256000 KB	Output is correct
14	Correct	1257 ms	256000 KB	Output is correct
15	Correct	1251 ms	256000 KB	Output is correct
16	Correct	777 ms	256000 KB	Output is correct
17	Correct	1259 ms	256000 KB	Output is correct
18	Correct	1141 ms	256000 KB	Output is correct
19	Correct	1537 ms	256000 KB	Output is correct
20	Correct	2412 ms	256000 KB	Output is correct
21	Correct	608 ms	256000 KB	Output is correct
22	Correct	2742 ms	256000 KB	Output is correct
23	Correct	573 ms	256000 KB	Output is correct
24	Correct	1627 ms	256000 KB	Output is correct
25	Correct	2642 ms	256000 KB	Output is correct
26	Correct	2363 ms	256000 KB	Output is correct
27	Correct	2110 ms	256000 KB	Output is correct
28	Correct	1221 ms	256000 KB	Output is correct
29	Correct	2719 ms	256000 KB	Output is correct
30	Correct	7067 ms	256000 KB	Output is correct
31	Correct	6396 ms	256000 KB	Output is correct
32	Correct	697 ms	256000 KB	Output is correct
33	Correct	970 ms	256000 KB	Output is correct
34	Correct	1710 ms	256000 KB	Output is correct
35	Correct	2079 ms	256000 KB	Output is correct
36	Correct	3897 ms	256000 KB	Output is correct
37	Correct	3205 ms	256000 KB	Output is correct
38	Correct	3153 ms	256000 KB	Output is correct
39	Execution timed out	9280 ms	256000 KB	Time limit exceeded (wall clock)
40	Halted	0 ms	0 KB	-

답안 #43172

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