oj.uz

답안 #121610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121610 2019-06-26T20:34:40 Z yusufake 게임 (IOI13_game) C++
80 / 100
 7254 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 + 7;
const int N   = 22000 * 37 * 37;
 
int Y[N],L[N],R[N],id=1;
ll s[N];
 
// 0 is empty node 
// s[0] should be ineffective element
// 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 qry_y(_, int ly, int ry) { 
	if(ly > tr || ry < tl || !v) return 0;
	if (ly <= tl && tr <= ry) return s[v];
	return __gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
}
ll qry_x(_, int lx, int rx, int ly, int ry) { 
	if(lx > tr || rx < tl) return 0;
	if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod, ly, ry);
	return __gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
}
 
void up_y(_, int posy, int r1, int r2, ll t){  
    if(tl == tr){
		s[v] = t == -1 ? __gcd(s[r1] , s[r2]) : t;
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,posy,L[r1],L[r2],t); }
	s[v] = __gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_, int posx, int posy, ll t){
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
		else          { if(!L[v]) L[v] = ++id; up_x(sol,posx,posy,t); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,posy,Y[ L[v] ],Y[ R[v] ],(tl==tr?t:-1));
}
 
 
void update(int posx, int posy, ll t){
	up_x(1,0,mod,posx,posy,t);
}	

ll calculate(int lx, int ly, int rx, int ry){
	return qry_x(1,0,mod,lx,rx,ly,ry);
}	
 
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, 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:21: note: in expansion of macro 'sol'
  return __gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
                     ^~~
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:40: note: in expansion of macro 'sag'
  return __gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
                                        ^~~
game.cpp: In function 'll qry_x(int, int, int, int, 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:21: note: in expansion of macro 'sol'
  return __gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
                     ^~~
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:46: note: in expansion of macro 'sag'
  return __gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
                                              ^~~
game.cpp: In function 'void up_y(int, int, int, int, int, int, ll)':
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,posy,R[r1],R[r2],t); }
            ^~
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,posy,R[r1],R[r2],t); }
                                              ^~~
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,posy,L[r1],L[r2],t); }
                                              ^~~
game.cpp: In function 'void up_x(int, int, int, int, int, ll)':
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,posx,posy,t); }
             ^~
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,posx,posy,t); }
                                               ^~~
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,posx,posy,t); }
                                               ^~~

Subtask #1
10.0 / 10.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 512 KB Output is correct
4 Correct 2 ms 304 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 612 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 432 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1113 ms 27272 KB Output is correct
5 Correct 822 ms 27556 KB Output is correct
6 Correct 1205 ms 24504 KB Output is correct
7 Correct 1318 ms 24256 KB Output is correct
8 Correct 816 ms 15384 KB Output is correct
9 Correct 1288 ms 24380 KB Output is correct
10 Correct 1200 ms 24020 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 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 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1695 ms 12616 KB Output is correct
13 Correct 2482 ms 5988 KB Output is correct
14 Correct 619 ms 1068 KB Output is correct
15 Correct 2845 ms 8904 KB Output is correct
16 Correct 657 ms 14592 KB Output is correct
17 Correct 1859 ms 10828 KB Output is correct
18 Correct 2863 ms 14844 KB Output is correct
19 Correct 2595 ms 14960 KB Output is correct
20 Correct 2382 ms 14320 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 612 KB Output is correct
3 Correct 4 ms 572 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 512 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 2 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1113 ms 27356 KB Output is correct
13 Correct 835 ms 27588 KB Output is correct
14 Correct 1224 ms 24552 KB Output is correct
15 Correct 1281 ms 24240 KB Output is correct
16 Correct 757 ms 15424 KB Output is correct
17 Correct 1245 ms 24500 KB Output is correct
18 Correct 1221 ms 23952 KB Output is correct
19 Correct 1692 ms 12492 KB Output is correct
20 Correct 2562 ms 5996 KB Output is correct
21 Correct 614 ms 1056 KB Output is correct
22 Correct 2846 ms 8984 KB Output is correct
23 Correct 665 ms 14648 KB Output is correct
24 Correct 1753 ms 10832 KB Output is correct
25 Correct 2923 ms 14836 KB Output is correct
26 Correct 2551 ms 15012 KB Output is correct
27 Correct 2340 ms 14344 KB Output is correct
28 Correct 1143 ms 157584 KB Output is correct
29 Correct 2841 ms 175964 KB Output is correct
30 Correct 7220 ms 119992 KB Output is correct
31 Correct 6824 ms 91660 KB Output is correct
32 Correct 678 ms 1300 KB Output is correct
33 Correct 901 ms 2780 KB Output is correct
34 Correct 1523 ms 172940 KB Output is correct
35 Correct 2141 ms 88140 KB Output is correct
36 Correct 4406 ms 173500 KB Output is correct
37 Correct 3383 ms 173372 KB Output is correct
38 Correct 3313 ms 172784 KB Output is correct
39 Correct 2833 ms 133304 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 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 384 KB Output is correct
6 Correct 3 ms 512 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 1112 ms 27372 KB Output is correct
13 Correct 837 ms 27732 KB Output is correct
14 Correct 1253 ms 24480 KB Output is correct
15 Correct 1293 ms 24272 KB Output is correct
16 Correct 826 ms 15492 KB Output is correct
17 Correct 1330 ms 24416 KB Output is correct
18 Correct 1179 ms 24172 KB Output is correct
19 Correct 1660 ms 12556 KB Output is correct
20 Correct 2482 ms 6100 KB Output is correct
21 Correct 628 ms 1188 KB Output is correct
22 Correct 2904 ms 9104 KB Output is correct
23 Correct 692 ms 14884 KB Output is correct
24 Correct 1739 ms 10960 KB Output is correct
25 Correct 2933 ms 15044 KB Output is correct
26 Correct 2645 ms 15144 KB Output is correct
27 Correct 2392 ms 14444 KB Output is correct
28 Correct 1171 ms 157688 KB Output is correct
29 Correct 2901 ms 175924 KB Output is correct
30 Correct 7254 ms 120000 KB Output is correct
31 Correct 6653 ms 91672 KB Output is correct
32 Correct 690 ms 1272 KB Output is correct
33 Correct 902 ms 2772 KB Output is correct
34 Correct 1537 ms 173008 KB Output is correct
35 Correct 2120 ms 88116 KB Output is correct
36 Correct 4054 ms 173428 KB Output is correct
37 Correct 3365 ms 173568 KB Output is correct
38 Correct 3315 ms 172900 KB Output is correct
39 Runtime error 1128 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -