oj.uz

Submission #43147

# Submission time Handle Problem Language Result Execution time Memory
43147 2018-03-09T14:07:23 Z yusufake Game (IOI13_game) C++
80 / 100
 10276 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 * 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, bool h){  // s[0] should contain ineffective element
	if(tl == tr){
		s[v] = h ? tt : gcd(s[r1] , s[r2]);
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,L[r1],L[r2],h); }
	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] ],(tl==tr));
}
 
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:34: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:34: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:39: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:39: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, bool)':
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,R[r1],R[r2],h); }
            ^
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,R[r1],R[r2],h); }
                                              ^
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,L[r1],L[r2],h); }
                                              ^
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:53: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:53: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:54: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 2 ms 376 KB Output is correct
2 Correct 4 ms 612 KB Output is correct
3 Correct 4 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 1 ms 856 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 1101 ms 32388 KB Output is correct
5 Correct 818 ms 36368 KB Output is correct
6 Correct 1318 ms 38068 KB Output is correct
7 Correct 1382 ms 42508 KB Output is correct
8 Correct 912 ms 42508 KB Output is correct
9 Correct 1305 ms 51612 KB Output is correct
10 Correct 1195 ms 55740 KB Output is correct
11 Correct 2 ms 55740 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 55740 KB Output is correct
2 Correct 4 ms 55740 KB Output is correct
3 Correct 5 ms 55740 KB Output is correct
4 Correct 2 ms 55740 KB Output is correct
5 Correct 2 ms 55740 KB Output is correct
6 Correct 4 ms 55740 KB Output is correct
7 Correct 2 ms 55740 KB Output is correct
8 Correct 1 ms 55740 KB Output is correct
9 Correct 3 ms 55740 KB Output is correct
10 Correct 2 ms 55740 KB Output is correct
11 Correct 3 ms 55740 KB Output is correct
12 Correct 1491 ms 55740 KB Output is correct
13 Correct 2477 ms 55740 KB Output is correct
14 Correct 594 ms 55740 KB Output is correct
15 Correct 2700 ms 57796 KB Output is correct
16 Correct 589 ms 67720 KB Output is correct
17 Correct 1597 ms 68680 KB Output is correct
18 Correct 2530 ms 77984 KB Output is correct
19 Correct 2437 ms 83564 KB Output is correct
20 Correct 2324 ms 88344 KB Output is correct
21 Correct 2 ms 88344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 88344 KB Output is correct
2 Correct 5 ms 88344 KB Output is correct
3 Correct 4 ms 88344 KB Output is correct
4 Correct 2 ms 88344 KB Output is correct
5 Correct 1 ms 88344 KB Output is correct
6 Correct 3 ms 88344 KB Output is correct
7 Correct 2 ms 88344 KB Output is correct
8 Correct 2 ms 88344 KB Output is correct
9 Correct 3 ms 88344 KB Output is correct
10 Correct 3 ms 88344 KB Output is correct
11 Correct 3 ms 88344 KB Output is correct
12 Correct 1130 ms 105724 KB Output is correct
13 Correct 814 ms 110028 KB Output is correct
14 Correct 1402 ms 111580 KB Output is correct
15 Correct 1461 ms 115980 KB Output is correct
16 Correct 921 ms 115980 KB Output is correct
17 Correct 1415 ms 125120 KB Output is correct
18 Correct 1296 ms 129116 KB Output is correct
19 Correct 1532 ms 129116 KB Output is correct
20 Correct 2459 ms 129116 KB Output is correct
21 Correct 597 ms 129116 KB Output is correct
22 Correct 2837 ms 131284 KB Output is correct
23 Correct 615 ms 141064 KB Output is correct
24 Correct 1685 ms 142232 KB Output is correct
25 Correct 2704 ms 151612 KB Output is correct
26 Correct 2506 ms 157064 KB Output is correct
27 Correct 2282 ms 161856 KB Output is correct
28 Correct 1235 ms 256000 KB Output is correct
29 Correct 2915 ms 256000 KB Output is correct
30 Correct 7274 ms 256000 KB Output is correct
31 Correct 6745 ms 256000 KB Output is correct
32 Correct 715 ms 256000 KB Output is correct
33 Correct 1036 ms 256000 KB Output is correct
34 Correct 1779 ms 256000 KB Output is correct
35 Correct 2147 ms 256000 KB Output is correct
36 Correct 4034 ms 256000 KB Output is correct
37 Correct 3274 ms 256000 KB Output is correct
38 Correct 3319 ms 256000 KB Output is correct
39 Correct 3027 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 2 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 1126 ms 256000 KB Output is correct
13 Correct 821 ms 256000 KB Output is correct
14 Correct 1318 ms 256000 KB Output is correct
15 Correct 1353 ms 256000 KB Output is correct
16 Correct 852 ms 256000 KB Output is correct
17 Correct 1351 ms 256000 KB Output is correct
18 Correct 1233 ms 256000 KB Output is correct
19 Correct 1554 ms 256000 KB Output is correct
20 Correct 2452 ms 256000 KB Output is correct
21 Correct 595 ms 256000 KB Output is correct
22 Correct 2793 ms 256000 KB Output is correct
23 Correct 609 ms 256000 KB Output is correct
24 Correct 1709 ms 256000 KB Output is correct
25 Correct 2775 ms 256000 KB Output is correct
26 Correct 2449 ms 256000 KB Output is correct
27 Correct 2218 ms 256000 KB Output is correct
28 Correct 1186 ms 256000 KB Output is correct
29 Correct 2869 ms 256000 KB Output is correct
30 Correct 7125 ms 256000 KB Output is correct
31 Correct 6637 ms 256000 KB Output is correct
32 Correct 684 ms 256000 KB Output is correct
33 Correct 965 ms 256000 KB Output is correct
34 Correct 1677 ms 256000 KB Output is correct
35 Correct 2118 ms 256000 KB Output is correct
36 Correct 3982 ms 256000 KB Output is correct
37 Correct 3606 ms 256000 KB Output is correct
38 Correct 3388 ms 256000 KB Output is correct
39 Execution timed out 10276 ms 256000 KB Time limit exceeded (wall clock)
40 Halted 0 ms 0 KB -