oj.uz

Submission #42769

# Submission time Handle Problem Language Result Execution time Memory
42769 2018-03-03T22:41:34 Z yusufake Game (IOI13_game) C++
80 / 100
 12715 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 * 500;
 
int Y[N],L[N],R[N],posx,posy,lx,ly,rx,ry,id=1;
ll s[N],tt;
 
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(_, 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:28:21: 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:34: 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:21: 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:34: 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:41: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:41: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:42: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:47: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:47: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:48: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 612 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 1 ms 612 KB Output is correct
6 Correct 4 ms 732 KB Output is correct
7 Correct 1 ms 732 KB Output is correct
8 Correct 1 ms 732 KB Output is correct
9 Correct 4 ms 732 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 1 ms 748 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 1084 ms 30576 KB Output is correct
5 Correct 819 ms 34652 KB Output is correct
6 Correct 1365 ms 36272 KB Output is correct
7 Correct 1250 ms 40684 KB Output is correct
8 Correct 813 ms 40684 KB Output is correct
9 Correct 1314 ms 49800 KB Output is correct
10 Correct 1199 ms 54048 KB Output is correct
11 Correct 2 ms 54048 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 54048 KB Output is correct
2 Correct 3 ms 54048 KB Output is correct
3 Correct 4 ms 54048 KB Output is correct
4 Correct 1 ms 54048 KB Output is correct
5 Correct 2 ms 54048 KB Output is correct
6 Correct 3 ms 54048 KB Output is correct
7 Correct 2 ms 54048 KB Output is correct
8 Correct 1 ms 54048 KB Output is correct
9 Correct 3 ms 54048 KB Output is correct
10 Correct 2 ms 54048 KB Output is correct
11 Correct 2 ms 54048 KB Output is correct
12 Correct 1643 ms 54048 KB Output is correct
13 Correct 2615 ms 54048 KB Output is correct
14 Correct 708 ms 54048 KB Output is correct
15 Correct 3035 ms 54048 KB Output is correct
16 Correct 686 ms 54048 KB Output is correct
17 Correct 1635 ms 54048 KB Output is correct
18 Correct 2703 ms 58600 KB Output is correct
19 Correct 2512 ms 64276 KB Output is correct
20 Correct 2140 ms 69084 KB Output is correct
21 Correct 2 ms 69084 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 69084 KB Output is correct
2 Correct 5 ms 69084 KB Output is correct
3 Correct 4 ms 69084 KB Output is correct
4 Correct 2 ms 69084 KB Output is correct
5 Correct 2 ms 69084 KB Output is correct
6 Correct 4 ms 69084 KB Output is correct
7 Correct 2 ms 69084 KB Output is correct
8 Correct 2 ms 69084 KB Output is correct
9 Correct 3 ms 69084 KB Output is correct
10 Correct 2 ms 69084 KB Output is correct
11 Correct 2 ms 69084 KB Output is correct
12 Correct 1132 ms 84660 KB Output is correct
13 Correct 857 ms 88652 KB Output is correct
14 Correct 1232 ms 90456 KB Output is correct
15 Correct 1287 ms 94716 KB Output is correct
16 Correct 822 ms 94716 KB Output is correct
17 Correct 1330 ms 103972 KB Output is correct
18 Correct 1245 ms 108076 KB Output is correct
19 Correct 1699 ms 108076 KB Output is correct
20 Correct 2720 ms 108076 KB Output is correct
21 Correct 690 ms 108076 KB Output is correct
22 Correct 3096 ms 110108 KB Output is correct
23 Correct 704 ms 120064 KB Output is correct
24 Correct 1589 ms 121080 KB Output is correct
25 Correct 2513 ms 130500 KB Output is correct
26 Correct 2285 ms 135916 KB Output is correct
27 Correct 2049 ms 140824 KB Output is correct
28 Correct 1170 ms 256000 KB Output is correct
29 Correct 2890 ms 256000 KB Output is correct
30 Correct 7797 ms 256000 KB Output is correct
31 Correct 7146 ms 256000 KB Output is correct
32 Correct 770 ms 256000 KB Output is correct
33 Correct 968 ms 256000 KB Output is correct
34 Correct 1703 ms 256000 KB Output is correct
35 Correct 1940 ms 256000 KB Output is correct
36 Correct 3893 ms 256000 KB Output is correct
37 Correct 3218 ms 256000 KB Output is correct
38 Correct 3131 ms 256000 KB Output is correct
39 Correct 2623 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 3 ms 256000 KB Output is correct
3 Correct 4 ms 256000 KB Output is correct
4 Correct 1 ms 256000 KB Output is correct
5 Correct 1 ms 256000 KB Output is correct
6 Correct 3 ms 256000 KB Output is correct
7 Correct 2 ms 256000 KB Output is correct
8 Correct 1 ms 256000 KB Output is correct
9 Correct 4 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 1129 ms 256000 KB Output is correct
13 Correct 862 ms 256000 KB Output is correct
14 Correct 1248 ms 256000 KB Output is correct
15 Correct 1271 ms 256000 KB Output is correct
16 Correct 781 ms 256000 KB Output is correct
17 Correct 1270 ms 256000 KB Output is correct
18 Correct 1134 ms 256000 KB Output is correct
19 Correct 1654 ms 256000 KB Output is correct
20 Correct 2656 ms 256000 KB Output is correct
21 Correct 687 ms 256000 KB Output is correct
22 Correct 3102 ms 256000 KB Output is correct
23 Correct 673 ms 256000 KB Output is correct
24 Correct 1632 ms 256000 KB Output is correct
25 Correct 2551 ms 256000 KB Output is correct
26 Correct 2235 ms 256000 KB Output is correct
27 Correct 2138 ms 256000 KB Output is correct
28 Correct 1302 ms 256000 KB Output is correct
29 Correct 2905 ms 256000 KB Output is correct
30 Correct 8093 ms 256000 KB Output is correct
31 Correct 7352 ms 256000 KB Output is correct
32 Correct 763 ms 256000 KB Output is correct
33 Correct 1018 ms 256000 KB Output is correct
34 Correct 1747 ms 256000 KB Output is correct
35 Correct 2238 ms 256000 KB Output is correct
36 Correct 3963 ms 256000 KB Output is correct
37 Correct 3220 ms 256000 KB Output is correct
38 Correct 3257 ms 256000 KB Output is correct
39 Execution timed out 12715 ms 256000 KB Time limit exceeded (wall clock)
40 Halted 0 ms 0 KB -