oj.uz

Submission #43172

# Submission time Handle Problem Language Result Execution time Memory
43172 2018-03-09T17:45:59 Z yusufake Game (IOI13_game) C++
80 / 100
 9280 ms 256000 KB 
#include<stddef.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
  
typedef long long ll;
 
const int mod = 1e9 + 7;
const int N   = 22000 * 525;
 
int Y[N],L[N],R[N],posx,posy,lx,ly,rx,ry,id=1;
ll s[N],tt;
 
inline ll gcd(ll u, ll v) {
    ll r;
    while (v != 0) { r = u % v; u = v; v = r; }
    return u;
}

inline 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));
}
inline 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){  // s[0] should contain ineffective element
	if(tl == tr){
		s[v] = r1 || r2 ? gcd(s[r1] , s[r2]) : tt;
		return;
	}
    int &l = L[v];
    int &r = R[v];
	if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
	else          { if(!l) l = ++id; up_y(l,tl,tm,L[r1],L[r2]); }
	s[v] = gcd(s[l] , s[r]);
}
void up_x(_){
    int &l = L[v];
    int &r = R[v];
	if(tl < tr){
		if(posx > tm) { if(!r) r = ++id; up_x(r,tm+1,tr); }
		else          { if(!l) l = ++id; up_x(l,tl,tm); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,Y[l],Y[r]);
}
 
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:28: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:28: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:33: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:33: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:43:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
            ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:43:42: note: in expansion of macro 'tm'
  if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
                                          ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:44:45: note: in expansion of macro 'tm'
  else          { if(!l) l = ++id; up_y(l,tl,tm,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:51:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!r) r = ++id; up_x(r,tm+1,tr); }
             ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:51:43: note: in expansion of macro 'tm'
   if(posx > tm) { if(!r) r = ++id; up_x(r,tm+1,tr); }
                                           ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:52:46: note: in expansion of macro 'tm'
   else          { if(!l) l = ++id; up_x(l,tl,tm); }
                                              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 4 ms 608 KB Output is correct
3 Correct 4 ms 812 KB Output is correct
4 Correct 2 ms 812 KB Output is correct
5 Correct 1 ms 812 KB Output is correct
6 Correct 3 ms 812 KB Output is correct
7 Correct 2 ms 812 KB Output is correct
8 Correct 2 ms 812 KB Output is correct
9 Correct 3 ms 812 KB Output is correct
10 Correct 2 ms 812 KB Output is correct
11 Correct 2 ms 812 KB Output is correct
12 Correct 1 ms 812 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 812 KB Output is correct
2 Correct 2 ms 812 KB Output is correct
3 Correct 2 ms 812 KB Output is correct
4 Correct 1117 ms 32124 KB Output is correct
5 Correct 805 ms 36140 KB Output is correct
6 Correct 1260 ms 37936 KB Output is correct
7 Correct 1306 ms 42188 KB Output is correct
8 Correct 812 ms 42188 KB Output is correct
9 Correct 1373 ms 51360 KB Output is correct
10 Correct 1156 ms 55440 KB Output is correct
11 Correct 2 ms 55440 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 55440 KB Output is correct
2 Correct 4 ms 55440 KB Output is correct
3 Correct 4 ms 55440 KB Output is correct
4 Correct 1 ms 55440 KB Output is correct
5 Correct 1 ms 55440 KB Output is correct
6 Correct 4 ms 55440 KB Output is correct
7 Correct 2 ms 55440 KB Output is correct
8 Correct 2 ms 55440 KB Output is correct
9 Correct 3 ms 55440 KB Output is correct
10 Correct 2 ms 55440 KB Output is correct
11 Correct 2 ms 55440 KB Output is correct
12 Correct 1490 ms 55440 KB Output is correct
13 Correct 2418 ms 55440 KB Output is correct
14 Correct 580 ms 55440 KB Output is correct
15 Correct 2763 ms 57552 KB Output is correct
16 Correct 646 ms 67424 KB Output is correct
17 Correct 1678 ms 68528 KB Output is correct
18 Correct 2716 ms 77964 KB Output is correct
19 Correct 2348 ms 83352 KB Output is correct
20 Correct 2099 ms 88008 KB Output is correct
21 Correct 2 ms 88008 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 88008 KB Output is correct
2 Correct 3 ms 88008 KB Output is correct
3 Correct 3 ms 88008 KB Output is correct
4 Correct 1 ms 88008 KB Output is correct
5 Correct 1 ms 88008 KB Output is correct
6 Correct 3 ms 88008 KB Output is correct
7 Correct 1 ms 88008 KB Output is correct
8 Correct 1 ms 88008 KB Output is correct
9 Correct 3 ms 88008 KB Output is correct
10 Correct 2 ms 88008 KB Output is correct
11 Correct 2 ms 88008 KB Output is correct
12 Correct 1034 ms 105480 KB Output is correct
13 Correct 790 ms 109552 KB Output is correct
14 Correct 1286 ms 111400 KB Output is correct
15 Correct 1306 ms 115552 KB Output is correct
16 Correct 773 ms 115552 KB Output is correct
17 Correct 1315 ms 124568 KB Output is correct
18 Correct 1100 ms 128880 KB Output is correct
19 Correct 1447 ms 128880 KB Output is correct
20 Correct 2396 ms 128880 KB Output is correct
21 Correct 589 ms 128880 KB Output is correct
22 Correct 2752 ms 131020 KB Output is correct
23 Correct 552 ms 140716 KB Output is correct
24 Correct 1547 ms 141780 KB Output is correct
25 Correct 2477 ms 151292 KB Output is correct
26 Correct 2222 ms 156700 KB Output is correct
27 Correct 2097 ms 161336 KB Output is correct
28 Correct 1142 ms 256000 KB Output is correct
29 Correct 2749 ms 256000 KB Output is correct
30 Correct 7020 ms 256000 KB Output is correct
31 Correct 6287 ms 256000 KB Output is correct
32 Correct 714 ms 256000 KB Output is correct
33 Correct 938 ms 256000 KB Output is correct
34 Correct 1741 ms 256000 KB Output is correct
35 Correct 2047 ms 256000 KB Output is correct
36 Correct 3661 ms 256000 KB Output is correct
37 Correct 3102 ms 256000 KB Output is correct
38 Correct 3107 ms 256000 KB Output is correct
39 Correct 2779 ms 256000 KB Output is correct
40 Correct 2 ms 256000 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory 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 2 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 1098 ms 256000 KB Output is correct
13 Correct 836 ms 256000 KB Output is correct
14 Correct 1257 ms 256000 KB Output is correct
15 Correct 1251 ms 256000 KB Output is correct
16 Correct 777 ms 256000 KB Output is correct
17 Correct 1259 ms 256000 KB Output is correct
18 Correct 1141 ms 256000 KB Output is correct
19 Correct 1537 ms 256000 KB Output is correct
20 Correct 2412 ms 256000 KB Output is correct
21 Correct 608 ms 256000 KB Output is correct
22 Correct 2742 ms 256000 KB Output is correct
23 Correct 573 ms 256000 KB Output is correct
24 Correct 1627 ms 256000 KB Output is correct
25 Correct 2642 ms 256000 KB Output is correct
26 Correct 2363 ms 256000 KB Output is correct
27 Correct 2110 ms 256000 KB Output is correct
28 Correct 1221 ms 256000 KB Output is correct
29 Correct 2719 ms 256000 KB Output is correct
30 Correct 7067 ms 256000 KB Output is correct
31 Correct 6396 ms 256000 KB Output is correct
32 Correct 697 ms 256000 KB Output is correct
33 Correct 970 ms 256000 KB Output is correct
34 Correct 1710 ms 256000 KB Output is correct
35 Correct 2079 ms 256000 KB Output is correct
36 Correct 3897 ms 256000 KB Output is correct
37 Correct 3205 ms 256000 KB Output is correct
38 Correct 3153 ms 256000 KB Output is correct
39 Execution timed out 9280 ms 256000 KB Time limit exceeded (wall clock)
40 Halted 0 ms 0 KB -