oj.uz

Submission #122194

# Submission time Handle Problem Language Result Execution time Memory
122194 2019-06-27T19:47:28 Z yusufake Game (IOI13_game) C++
80 / 100
 13000 ms 232988 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(_, ll t){  
    if(id == N-2) while(1);
    if(tl == tr){
		s[v] = t;
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,t); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,t); }
	s[v] = gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_){
    if(id == N-2) while(1);
	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,(tl==tr?t:gcd(qry_y(Y[ L[v] ],0,mod) , qry_y(Y[ R[v] ],0,mod))));
}
 
 
void update(int px, int py, ll tt){
    posx = px;
    posy = py;
    t = tt;
    ly = ry = posy;
	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, ll)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:55:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,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:55:46: note: in expansion of macro 'sag'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,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:56:46: note: in expansion of macro 'sol'
  else          { if(!L[v]) L[v] = ++id; up_y(sol,t); }
                                              ^~~
game.cpp: In function 'void up_x(int, int, int)':
game.cpp:60:19: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     if(id == N-2) while(1);
                   ^~~~~
game.cpp:61: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:62: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:62: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:63:47: note: in expansion of macro 'sol'
   else          { if(!L[v]) L[v] = ++id; up_x(sol); }
                                               ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 5 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 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 1149 ms 31224 KB Output is correct
5 Correct 905 ms 30884 KB Output is correct
6 Correct 1299 ms 28616 KB Output is correct
7 Correct 1333 ms 28280 KB Output is correct
8 Correct 800 ms 19108 KB Output is correct
9 Correct 1350 ms 28536 KB Output is correct
10 Correct 1219 ms 28232 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 540 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 4 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1670 ms 16064 KB Output is correct
13 Correct 2482 ms 9464 KB Output is correct
14 Correct 653 ms 5240 KB Output is correct
15 Correct 2813 ms 12668 KB Output is correct
16 Correct 744 ms 18264 KB Output is correct
17 Correct 1571 ms 15020 KB Output is correct
18 Correct 2637 ms 19456 KB Output is correct
19 Correct 2295 ms 19756 KB Output is correct
20 Correct 2265 ms 18924 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 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 5 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 508 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1124 ms 31244 KB Output is correct
13 Correct 869 ms 30940 KB Output is correct
14 Correct 1253 ms 28664 KB Output is correct
15 Correct 1315 ms 28468 KB Output is correct
16 Correct 787 ms 19144 KB Output is correct
17 Correct 1336 ms 28520 KB Output is correct
18 Correct 1246 ms 28072 KB Output is correct
19 Correct 1638 ms 16048 KB Output is correct
20 Correct 2473 ms 9828 KB Output is correct
21 Correct 652 ms 5132 KB Output is correct
22 Correct 2817 ms 12728 KB Output is correct
23 Correct 756 ms 18424 KB Output is correct
24 Correct 1674 ms 14992 KB Output is correct
25 Correct 2927 ms 19612 KB Output is correct
26 Correct 2624 ms 19652 KB Output is correct
27 Correct 2421 ms 19248 KB Output is correct
28 Correct 1212 ms 164872 KB Output is correct
29 Correct 2850 ms 182412 KB Output is correct
30 Correct 6792 ms 124804 KB Output is correct
31 Correct 6293 ms 96592 KB Output is correct
32 Correct 757 ms 7536 KB Output is correct
33 Correct 960 ms 9080 KB Output is correct
34 Correct 732 ms 177816 KB Output is correct
35 Correct 2016 ms 94980 KB Output is correct
36 Correct 4085 ms 181372 KB Output is correct
37 Correct 3334 ms 181568 KB Output is correct
38 Correct 3338 ms 180728 KB Output is correct
39 Correct 2951 ms 141404 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 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 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 1152 ms 31340 KB Output is correct
13 Correct 905 ms 30944 KB Output is correct
14 Correct 1241 ms 28640 KB Output is correct
15 Correct 1291 ms 28348 KB Output is correct
16 Correct 801 ms 19160 KB Output is correct
17 Correct 1382 ms 28660 KB Output is correct
18 Correct 1244 ms 28280 KB Output is correct
19 Correct 1658 ms 16252 KB Output is correct
20 Correct 2480 ms 9492 KB Output is correct
21 Correct 659 ms 5368 KB Output is correct
22 Correct 2801 ms 12852 KB Output is correct
23 Correct 755 ms 18248 KB Output is correct
24 Correct 1615 ms 15324 KB Output is correct
25 Correct 2817 ms 19656 KB Output is correct
26 Correct 2466 ms 19756 KB Output is correct
27 Correct 2163 ms 19180 KB Output is correct
28 Correct 1169 ms 166168 KB Output is correct
29 Correct 2826 ms 183528 KB Output is correct
30 Correct 7303 ms 125092 KB Output is correct
31 Correct 6259 ms 96976 KB Output is correct
32 Correct 741 ms 8312 KB Output is correct
33 Correct 946 ms 9896 KB Output is correct
34 Correct 852 ms 178656 KB Output is correct
35 Correct 2270 ms 95872 KB Output is correct
36 Correct 4490 ms 180968 KB Output is correct
37 Correct 3565 ms 180688 KB Output is correct
38 Correct 3266 ms 180524 KB Output is correct
39 Execution timed out 13113 ms 232988 KB Time limit exceeded
40 Halted 0 ms 0 KB -