oj.uz

답안 #121634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121634 2019-06-26T21:16:01 Z yusufake 게임 (IOI13_game) C++14
80 / 100
 7413 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 * 61 * 61;

int Y[N],L[N],R[N],id=1;
ll s[N];
 
// 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
 
inline ll gcd(ll u, ll v) {
    ll r;
    while (v != 0) { r = u % v; u = v; v = r; }
    return u;
} 
 
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(id == 22000 * 61 * 61 - 5) while(1);
    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(id == 22000 * 61 * 61 - 5) while(1);
	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:40:19: 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:40:38: 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:45:19: 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:45:44: 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:54: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:54: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:55: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:59:35: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     if(id == 22000 * 61 * 61 - 5) while(1);
                                   ^~~~~
game.cpp:60:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  if(tl < tr){
  ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:61: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:61: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:62: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 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 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 2 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 2 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 1155 ms 28204 KB Output is correct
5 Correct 889 ms 28756 KB Output is correct
6 Correct 1265 ms 25808 KB Output is correct
7 Correct 1286 ms 25844 KB Output is correct
8 Correct 786 ms 16916 KB Output is correct
9 Correct 1286 ms 26212 KB Output is correct
10 Correct 1163 ms 25708 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 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 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 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1675 ms 13956 KB Output is correct
13 Correct 2540 ms 7328 KB Output is correct
14 Correct 622 ms 2624 KB Output is correct
15 Correct 2929 ms 10448 KB Output is correct
16 Correct 743 ms 16128 KB Output is correct
17 Correct 1794 ms 12320 KB Output is correct
18 Correct 2879 ms 16508 KB Output is correct
19 Correct 2736 ms 16708 KB Output is correct
20 Correct 2521 ms 16060 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 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 2 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1114 ms 29008 KB Output is correct
13 Correct 851 ms 28948 KB Output is correct
14 Correct 1248 ms 26568 KB Output is correct
15 Correct 1266 ms 26372 KB Output is correct
16 Correct 814 ms 17216 KB Output is correct
17 Correct 1261 ms 26728 KB Output is correct
18 Correct 1153 ms 26092 KB Output is correct
19 Correct 1693 ms 14292 KB Output is correct
20 Correct 2485 ms 7452 KB Output is correct
21 Correct 623 ms 3080 KB Output is correct
22 Correct 2889 ms 10808 KB Output is correct
23 Correct 678 ms 16288 KB Output is correct
24 Correct 1760 ms 13048 KB Output is correct
25 Correct 2937 ms 16876 KB Output is correct
26 Correct 2705 ms 16944 KB Output is correct
27 Correct 2426 ms 15284 KB Output is correct
28 Correct 1148 ms 158488 KB Output is correct
29 Correct 2925 ms 176588 KB Output is correct
30 Correct 7413 ms 121096 KB Output is correct
31 Correct 6668 ms 93300 KB Output is correct
32 Correct 717 ms 2856 KB Output is correct
33 Correct 922 ms 4484 KB Output is correct
34 Correct 1544 ms 174892 KB Output is correct
35 Correct 2167 ms 90024 KB Output is correct
36 Correct 4141 ms 175592 KB Output is correct
37 Correct 3353 ms 175168 KB Output is correct
38 Correct 3419 ms 174844 KB Output is correct
39 Correct 2999 ms 135256 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 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 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 2 ms 512 KB Output is correct
11 Correct 3 ms 480 KB Output is correct
12 Correct 1089 ms 28736 KB Output is correct
13 Correct 835 ms 28904 KB Output is correct
14 Correct 1256 ms 25912 KB Output is correct
15 Correct 1264 ms 25716 KB Output is correct
16 Correct 801 ms 16896 KB Output is correct
17 Correct 1324 ms 26016 KB Output is correct
18 Correct 1177 ms 25928 KB Output is correct
19 Correct 1691 ms 14780 KB Output is correct
20 Correct 2468 ms 8104 KB Output is correct
21 Correct 612 ms 3252 KB Output is correct
22 Correct 2867 ms 10932 KB Output is correct
23 Correct 707 ms 16540 KB Output is correct
24 Correct 1709 ms 12844 KB Output is correct
25 Correct 2981 ms 16872 KB Output is correct
26 Correct 2498 ms 16824 KB Output is correct
27 Correct 2507 ms 16008 KB Output is correct
28 Correct 1312 ms 159456 KB Output is correct
29 Correct 2896 ms 177456 KB Output is correct
30 Correct 7352 ms 121676 KB Output is correct
31 Correct 6745 ms 93228 KB Output is correct
32 Correct 693 ms 2680 KB Output is correct
33 Correct 912 ms 4180 KB Output is correct
34 Correct 1545 ms 173584 KB Output is correct
35 Correct 2168 ms 88944 KB Output is correct
36 Correct 4278 ms 174412 KB Output is correct
37 Correct 3663 ms 174520 KB Output is correct
38 Correct 3323 ms 174528 KB Output is correct
39 Runtime error 1125 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -