oj.uz

답안 #122144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122144 2019-06-27T16:59:37 Z yusufake 게임 (IOI13_game) C++
80 / 100
 6895 ms 256000 KB 
#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 - 1;
const int N   = 22000 * 23 * 23;
 
int Y[N],L[N],R[N],id = 1;
ll s[N],t;
int posx,posy,lx,rx,ly,ry;
 
// 0 is empty node 
// s[0] should be ineffective element
// Y[0], L[0], and R[0] should be 0
// 1 is the root of the -x axis segment tree
// Y[v] is the root of the segment tree of the interval that corresponds to node 'v' in -x axis segment tree
 
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){  
    if(tl == tr){
		s[v] = r1 || r2 ? gcd(s[r1] , s[r2]) : t;
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2]); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,L[r1],L[r2]); }
	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] ]);
}
 
 
void update(int px, int py, ll tt){
    posx = px;
    posy = py;
    t = tt;
	up_x(1,0,mod);
}	
 
ll calculate(int aalx, int aaly, int aarx, int aary){
    lx = aalx; rx = aarx;
    ly = aaly; ry = aary;
	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:41: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:41: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:46: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:46: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:54:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2]); }
            ^~
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:54:46: note: in expansion of macro 'sag'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2]); }
                                              ^~~
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:55:46: note: in expansion of macro 'sol'
  else          { if(!L[v]) L[v] = ++id; up_y(sol,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:60: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:60: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:61: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 256 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 356 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1068 ms 28316 KB Output is correct
5 Correct 794 ms 28536 KB Output is correct
6 Correct 1188 ms 25636 KB Output is correct
7 Correct 1311 ms 25356 KB Output is correct
8 Correct 809 ms 16228 KB Output is correct
9 Correct 1378 ms 25592 KB Output is correct
10 Correct 1170 ms 25284 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 612 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1536 ms 13532 KB Output is correct
13 Correct 2402 ms 7328 KB Output is correct
14 Correct 563 ms 2296 KB Output is correct
15 Correct 2715 ms 10280 KB Output is correct
16 Correct 620 ms 15956 KB Output is correct
17 Correct 1662 ms 12340 KB Output is correct
18 Correct 2922 ms 16396 KB Output is correct
19 Correct 2352 ms 16496 KB Output is correct
20 Correct 2302 ms 15960 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1093 ms 28268 KB Output is correct
13 Correct 862 ms 28552 KB Output is correct
14 Correct 1221 ms 26108 KB Output is correct
15 Correct 1238 ms 25708 KB Output is correct
16 Correct 774 ms 16568 KB Output is correct
17 Correct 1291 ms 26008 KB Output is correct
18 Correct 1122 ms 25592 KB Output is correct
19 Correct 1534 ms 13524 KB Output is correct
20 Correct 2329 ms 7384 KB Output is correct
21 Correct 548 ms 2424 KB Output is correct
22 Correct 2661 ms 10476 KB Output is correct
23 Correct 636 ms 15828 KB Output is correct
24 Correct 1622 ms 12096 KB Output is correct
25 Correct 2843 ms 16272 KB Output is correct
26 Correct 2520 ms 16244 KB Output is correct
27 Correct 2342 ms 15848 KB Output is correct
28 Correct 1118 ms 159348 KB Output is correct
29 Correct 2695 ms 178168 KB Output is correct
30 Correct 6735 ms 121752 KB Output is correct
31 Correct 6036 ms 93324 KB Output is correct
32 Correct 610 ms 3448 KB Output is correct
33 Correct 820 ms 5116 KB Output is correct
34 Correct 545 ms 174456 KB Output is correct
35 Correct 2193 ms 90528 KB Output is correct
36 Correct 4274 ms 175728 KB Output is correct
37 Correct 3521 ms 176256 KB Output is correct
38 Correct 3580 ms 175724 KB Output is correct
39 Correct 2888 ms 136064 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1016 ms 28904 KB Output is correct
13 Correct 913 ms 29176 KB Output is correct
14 Correct 1245 ms 26104 KB Output is correct
15 Correct 1317 ms 25792 KB Output is correct
16 Correct 779 ms 17060 KB Output is correct
17 Correct 1465 ms 26116 KB Output is correct
18 Correct 1159 ms 25568 KB Output is correct
19 Correct 1569 ms 14052 KB Output is correct
20 Correct 2416 ms 7720 KB Output is correct
21 Correct 571 ms 2680 KB Output is correct
22 Correct 2735 ms 10680 KB Output is correct
23 Correct 628 ms 16120 KB Output is correct
24 Correct 1632 ms 12692 KB Output is correct
25 Correct 2786 ms 16524 KB Output is correct
26 Correct 2411 ms 16980 KB Output is correct
27 Correct 2139 ms 16212 KB Output is correct
28 Correct 1082 ms 160480 KB Output is correct
29 Correct 2647 ms 178416 KB Output is correct
30 Correct 6895 ms 121492 KB Output is correct
31 Correct 6326 ms 93480 KB Output is correct
32 Correct 610 ms 3960 KB Output is correct
33 Correct 802 ms 5548 KB Output is correct
34 Correct 546 ms 175352 KB Output is correct
35 Correct 2001 ms 91032 KB Output is correct
36 Correct 4503 ms 176608 KB Output is correct
37 Correct 3251 ms 176860 KB Output is correct
38 Correct 3313 ms 176400 KB Output is correct
39 Runtime error 1320 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -