답안 #42770 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42770	2018-03-03T22:51:17 Z	yusufake	게임 (IOI13_game)	C++	80 / 100	12002 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 gcd(ll u, ll v) {
    ll r;
    while ( v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

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:38: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:38: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:43: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:43: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:51: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:51: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:52: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:57: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:57: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:58: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	608 KB	Output is correct
3	Correct	4 ms	680 KB	Output is correct
4	Correct	1 ms	680 KB	Output is correct
5	Correct	2 ms	680 KB	Output is correct
6	Correct	3 ms	680 KB	Output is correct
7	Correct	1 ms	680 KB	Output is correct
8	Correct	1 ms	680 KB	Output is correct
9	Correct	4 ms	788 KB	Output is correct
10	Correct	2 ms	788 KB	Output is correct
11	Correct	2 ms	788 KB	Output is correct
12	Correct	1 ms	788 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	788 KB	Output is correct
2	Correct	1 ms	788 KB	Output is correct
3	Correct	1 ms	788 KB	Output is correct
4	Correct	1146 ms	30448 KB	Output is correct
5	Correct	871 ms	34624 KB	Output is correct
6	Correct	1247 ms	36160 KB	Output is correct
7	Correct	1238 ms	40740 KB	Output is correct
8	Correct	822 ms	40740 KB	Output is correct
9	Correct	1274 ms	49580 KB	Output is correct
10	Correct	1199 ms	54040 KB	Output is correct
11	Correct	2 ms	54040 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	54040 KB	Output is correct
2	Correct	4 ms	54040 KB	Output is correct
3	Correct	4 ms	54040 KB	Output is correct
4	Correct	1 ms	54040 KB	Output is correct
5	Correct	1 ms	54040 KB	Output is correct
6	Correct	4 ms	54040 KB	Output is correct
7	Correct	2 ms	54040 KB	Output is correct
8	Correct	1 ms	54040 KB	Output is correct
9	Correct	3 ms	54040 KB	Output is correct
10	Correct	3 ms	54040 KB	Output is correct
11	Correct	2 ms	54040 KB	Output is correct
12	Correct	1815 ms	54040 KB	Output is correct
13	Correct	2744 ms	54040 KB	Output is correct
14	Correct	661 ms	54040 KB	Output is correct
15	Correct	3269 ms	54040 KB	Output is correct
16	Correct	698 ms	54040 KB	Output is correct
17	Correct	1711 ms	54040 KB	Output is correct
18	Correct	2708 ms	58796 KB	Output is correct
19	Correct	2379 ms	64228 KB	Output is correct
20	Correct	2259 ms	68832 KB	Output is correct
21	Correct	2 ms	68832 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	68832 KB	Output is correct
2	Correct	4 ms	68832 KB	Output is correct
3	Correct	4 ms	68832 KB	Output is correct
4	Correct	2 ms	68832 KB	Output is correct
5	Correct	2 ms	68832 KB	Output is correct
6	Correct	3 ms	68832 KB	Output is correct
7	Correct	2 ms	68832 KB	Output is correct
8	Correct	2 ms	68832 KB	Output is correct
9	Correct	3 ms	68832 KB	Output is correct
10	Correct	2 ms	68832 KB	Output is correct
11	Correct	2 ms	68832 KB	Output is correct
12	Correct	1237 ms	84696 KB	Output is correct
13	Correct	883 ms	88772 KB	Output is correct
14	Correct	1299 ms	90404 KB	Output is correct
15	Correct	1307 ms	94752 KB	Output is correct
16	Correct	820 ms	94752 KB	Output is correct
17	Correct	1296 ms	103892 KB	Output is correct
18	Correct	1201 ms	108160 KB	Output is correct
19	Correct	1725 ms	108160 KB	Output is correct
20	Correct	2770 ms	108160 KB	Output is correct
21	Correct	686 ms	108160 KB	Output is correct
22	Correct	3251 ms	110048 KB	Output is correct
23	Correct	748 ms	120080 KB	Output is correct
24	Correct	1707 ms	121096 KB	Output is correct
25	Correct	2782 ms	130488 KB	Output is correct
26	Correct	2446 ms	135952 KB	Output is correct
27	Correct	2296 ms	140676 KB	Output is correct
28	Correct	1203 ms	256000 KB	Output is correct
29	Correct	2866 ms	256000 KB	Output is correct
30	Correct	8239 ms	256000 KB	Output is correct
31	Correct	7566 ms	256000 KB	Output is correct
32	Correct	761 ms	256000 KB	Output is correct
33	Correct	1008 ms	256000 KB	Output is correct
34	Correct	1750 ms	256000 KB	Output is correct
35	Correct	2045 ms	256000 KB	Output is correct
36	Correct	3932 ms	256000 KB	Output is correct
37	Correct	3171 ms	256000 KB	Output is correct
38	Correct	3094 ms	256000 KB	Output is correct
39	Correct	2678 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	1 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	1160 ms	256000 KB	Output is correct
13	Correct	912 ms	256000 KB	Output is correct
14	Correct	1314 ms	256000 KB	Output is correct
15	Correct	1405 ms	256000 KB	Output is correct
16	Correct	812 ms	256000 KB	Output is correct
17	Correct	1339 ms	256000 KB	Output is correct
18	Correct	1177 ms	256000 KB	Output is correct
19	Correct	1747 ms	256000 KB	Output is correct
20	Correct	2810 ms	256000 KB	Output is correct
21	Correct	686 ms	256000 KB	Output is correct
22	Correct	3204 ms	256000 KB	Output is correct
23	Correct	701 ms	256000 KB	Output is correct
24	Correct	1658 ms	256000 KB	Output is correct
25	Correct	2596 ms	256000 KB	Output is correct
26	Correct	2316 ms	256000 KB	Output is correct
27	Correct	2168 ms	256000 KB	Output is correct
28	Correct	1164 ms	256000 KB	Output is correct
29	Correct	2902 ms	256000 KB	Output is correct
30	Correct	8237 ms	256000 KB	Output is correct
31	Correct	7533 ms	256000 KB	Output is correct
32	Correct	793 ms	256000 KB	Output is correct
33	Correct	1010 ms	256000 KB	Output is correct
34	Correct	1723 ms	256000 KB	Output is correct
35	Correct	2075 ms	256000 KB	Output is correct
36	Correct	3821 ms	256000 KB	Output is correct
37	Correct	3342 ms	256000 KB	Output is correct
38	Correct	3198 ms	256000 KB	Output is correct
39	Runtime error	12002 ms	256000 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-

답안 #42770

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