답안 #42769 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42769	2018-03-03T22:41:34 Z	yusufake	게임 (IOI13_game)	C++	80 / 100	12715 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 * 500;
 
int Y[N],L[N],R[N],posx,posy,lx,ly,rx,ry,id=1;
ll s[N],tt;
 
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));
}
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:28:21: 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:34: 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:21: 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:34: 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:41: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:41: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:42: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:47: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:47: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:48: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	612 KB	Output is correct
4	Correct	2 ms	612 KB	Output is correct
5	Correct	1 ms	612 KB	Output is correct
6	Correct	4 ms	732 KB	Output is correct
7	Correct	1 ms	732 KB	Output is correct
8	Correct	1 ms	732 KB	Output is correct
9	Correct	4 ms	732 KB	Output is correct
10	Correct	3 ms	748 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	1 ms	748 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	1 ms	748 KB	Output is correct
3	Correct	2 ms	748 KB	Output is correct
4	Correct	1084 ms	30576 KB	Output is correct
5	Correct	819 ms	34652 KB	Output is correct
6	Correct	1365 ms	36272 KB	Output is correct
7	Correct	1250 ms	40684 KB	Output is correct
8	Correct	813 ms	40684 KB	Output is correct
9	Correct	1314 ms	49800 KB	Output is correct
10	Correct	1199 ms	54048 KB	Output is correct
11	Correct	2 ms	54048 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	54048 KB	Output is correct
2	Correct	3 ms	54048 KB	Output is correct
3	Correct	4 ms	54048 KB	Output is correct
4	Correct	1 ms	54048 KB	Output is correct
5	Correct	2 ms	54048 KB	Output is correct
6	Correct	3 ms	54048 KB	Output is correct
7	Correct	2 ms	54048 KB	Output is correct
8	Correct	1 ms	54048 KB	Output is correct
9	Correct	3 ms	54048 KB	Output is correct
10	Correct	2 ms	54048 KB	Output is correct
11	Correct	2 ms	54048 KB	Output is correct
12	Correct	1643 ms	54048 KB	Output is correct
13	Correct	2615 ms	54048 KB	Output is correct
14	Correct	708 ms	54048 KB	Output is correct
15	Correct	3035 ms	54048 KB	Output is correct
16	Correct	686 ms	54048 KB	Output is correct
17	Correct	1635 ms	54048 KB	Output is correct
18	Correct	2703 ms	58600 KB	Output is correct
19	Correct	2512 ms	64276 KB	Output is correct
20	Correct	2140 ms	69084 KB	Output is correct
21	Correct	2 ms	69084 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	69084 KB	Output is correct
2	Correct	5 ms	69084 KB	Output is correct
3	Correct	4 ms	69084 KB	Output is correct
4	Correct	2 ms	69084 KB	Output is correct
5	Correct	2 ms	69084 KB	Output is correct
6	Correct	4 ms	69084 KB	Output is correct
7	Correct	2 ms	69084 KB	Output is correct
8	Correct	2 ms	69084 KB	Output is correct
9	Correct	3 ms	69084 KB	Output is correct
10	Correct	2 ms	69084 KB	Output is correct
11	Correct	2 ms	69084 KB	Output is correct
12	Correct	1132 ms	84660 KB	Output is correct
13	Correct	857 ms	88652 KB	Output is correct
14	Correct	1232 ms	90456 KB	Output is correct
15	Correct	1287 ms	94716 KB	Output is correct
16	Correct	822 ms	94716 KB	Output is correct
17	Correct	1330 ms	103972 KB	Output is correct
18	Correct	1245 ms	108076 KB	Output is correct
19	Correct	1699 ms	108076 KB	Output is correct
20	Correct	2720 ms	108076 KB	Output is correct
21	Correct	690 ms	108076 KB	Output is correct
22	Correct	3096 ms	110108 KB	Output is correct
23	Correct	704 ms	120064 KB	Output is correct
24	Correct	1589 ms	121080 KB	Output is correct
25	Correct	2513 ms	130500 KB	Output is correct
26	Correct	2285 ms	135916 KB	Output is correct
27	Correct	2049 ms	140824 KB	Output is correct
28	Correct	1170 ms	256000 KB	Output is correct
29	Correct	2890 ms	256000 KB	Output is correct
30	Correct	7797 ms	256000 KB	Output is correct
31	Correct	7146 ms	256000 KB	Output is correct
32	Correct	770 ms	256000 KB	Output is correct
33	Correct	968 ms	256000 KB	Output is correct
34	Correct	1703 ms	256000 KB	Output is correct
35	Correct	1940 ms	256000 KB	Output is correct
36	Correct	3893 ms	256000 KB	Output is correct
37	Correct	3218 ms	256000 KB	Output is correct
38	Correct	3131 ms	256000 KB	Output is correct
39	Correct	2623 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	3 ms	256000 KB	Output is correct
3	Correct	4 ms	256000 KB	Output is correct
4	Correct	1 ms	256000 KB	Output is correct
5	Correct	1 ms	256000 KB	Output is correct
6	Correct	3 ms	256000 KB	Output is correct
7	Correct	2 ms	256000 KB	Output is correct
8	Correct	1 ms	256000 KB	Output is correct
9	Correct	4 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	1129 ms	256000 KB	Output is correct
13	Correct	862 ms	256000 KB	Output is correct
14	Correct	1248 ms	256000 KB	Output is correct
15	Correct	1271 ms	256000 KB	Output is correct
16	Correct	781 ms	256000 KB	Output is correct
17	Correct	1270 ms	256000 KB	Output is correct
18	Correct	1134 ms	256000 KB	Output is correct
19	Correct	1654 ms	256000 KB	Output is correct
20	Correct	2656 ms	256000 KB	Output is correct
21	Correct	687 ms	256000 KB	Output is correct
22	Correct	3102 ms	256000 KB	Output is correct
23	Correct	673 ms	256000 KB	Output is correct
24	Correct	1632 ms	256000 KB	Output is correct
25	Correct	2551 ms	256000 KB	Output is correct
26	Correct	2235 ms	256000 KB	Output is correct
27	Correct	2138 ms	256000 KB	Output is correct
28	Correct	1302 ms	256000 KB	Output is correct
29	Correct	2905 ms	256000 KB	Output is correct
30	Correct	8093 ms	256000 KB	Output is correct
31	Correct	7352 ms	256000 KB	Output is correct
32	Correct	763 ms	256000 KB	Output is correct
33	Correct	1018 ms	256000 KB	Output is correct
34	Correct	1747 ms	256000 KB	Output is correct
35	Correct	2238 ms	256000 KB	Output is correct
36	Correct	3963 ms	256000 KB	Output is correct
37	Correct	3220 ms	256000 KB	Output is correct
38	Correct	3257 ms	256000 KB	Output is correct
39	Execution timed out	12715 ms	256000 KB	Time limit exceeded (wall clock)
40	Halted	0 ms	0 KB	-

답안 #42769

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