oj.uz

Submission #42768

# Submission time Handle Problem Language Result Execution time Memory
42768 2018-03-03T22:35:03 Z yusufake Game (IOI13_game) C++
80 / 100
 8045 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 * 440;
 
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){
		if(h) s[v] = tt;
		else s[v] = __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:42: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:42: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:43: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:48: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:48: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:49: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 5 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 2 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 1150 ms 30492 KB Output is correct
5 Correct 921 ms 34768 KB Output is correct
6 Correct 1311 ms 36208 KB Output is correct
7 Correct 1371 ms 40868 KB Output is correct
8 Correct 836 ms 40868 KB Output is correct
9 Correct 1289 ms 49764 KB Output is correct
10 Correct 1138 ms 54092 KB Output is correct
11 Correct 2 ms 54092 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 54092 KB Output is correct
2 Correct 4 ms 54092 KB Output is correct
3 Correct 3 ms 54092 KB Output is correct
4 Correct 1 ms 54092 KB Output is correct
5 Correct 1 ms 54092 KB Output is correct
6 Correct 4 ms 54092 KB Output is correct
7 Correct 2 ms 54092 KB Output is correct
8 Correct 1 ms 54092 KB Output is correct
9 Correct 3 ms 54092 KB Output is correct
10 Correct 2 ms 54092 KB Output is correct
11 Correct 2 ms 54092 KB Output is correct
12 Correct 1663 ms 54092 KB Output is correct
13 Correct 2720 ms 54092 KB Output is correct
14 Correct 685 ms 54092 KB Output is correct
15 Correct 3115 ms 54092 KB Output is correct
16 Correct 684 ms 54092 KB Output is correct
17 Correct 1701 ms 54092 KB Output is correct
18 Correct 2622 ms 58712 KB Output is correct
19 Correct 2297 ms 64240 KB Output is correct
20 Correct 2253 ms 69008 KB Output is correct
21 Correct 2 ms 69008 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 69008 KB Output is correct
2 Correct 4 ms 69008 KB Output is correct
3 Correct 5 ms 69008 KB Output is correct
4 Correct 1 ms 69008 KB Output is correct
5 Correct 1 ms 69008 KB Output is correct
6 Correct 3 ms 69008 KB Output is correct
7 Correct 2 ms 69008 KB Output is correct
8 Correct 2 ms 69008 KB Output is correct
9 Correct 3 ms 69008 KB Output is correct
10 Correct 3 ms 69008 KB Output is correct
11 Correct 2 ms 69008 KB Output is correct
12 Correct 1096 ms 84628 KB Output is correct
13 Correct 840 ms 88820 KB Output is correct
14 Correct 1261 ms 90572 KB Output is correct
15 Correct 1302 ms 94748 KB Output is correct
16 Correct 807 ms 94748 KB Output is correct
17 Correct 1310 ms 103808 KB Output is correct
18 Correct 1162 ms 107988 KB Output is correct
19 Correct 1693 ms 107988 KB Output is correct
20 Correct 2681 ms 107988 KB Output is correct
21 Correct 665 ms 107988 KB Output is correct
22 Correct 3078 ms 110312 KB Output is correct
23 Correct 670 ms 120116 KB Output is correct
24 Correct 1591 ms 121100 KB Output is correct
25 Correct 2585 ms 130648 KB Output is correct
26 Correct 2278 ms 135952 KB Output is correct
27 Correct 2294 ms 140696 KB Output is correct
28 Correct 1203 ms 256000 KB Output is correct
29 Correct 2917 ms 256000 KB Output is correct
30 Correct 7906 ms 256000 KB Output is correct
31 Correct 7194 ms 256000 KB Output is correct
32 Correct 757 ms 256000 KB Output is correct
33 Correct 998 ms 256000 KB Output is correct
34 Correct 1737 ms 256000 KB Output is correct
35 Correct 2001 ms 256000 KB Output is correct
36 Correct 3794 ms 256000 KB Output is correct
37 Correct 3070 ms 256000 KB Output is correct
38 Correct 3050 ms 256000 KB Output is correct
39 Correct 2514 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 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 1 ms 256000 KB Output is correct
8 Correct 1 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 1090 ms 256000 KB Output is correct
13 Correct 815 ms 256000 KB Output is correct
14 Correct 1235 ms 256000 KB Output is correct
15 Correct 1230 ms 256000 KB Output is correct
16 Correct 812 ms 256000 KB Output is correct
17 Correct 1292 ms 256000 KB Output is correct
18 Correct 1158 ms 256000 KB Output is correct
19 Correct 1704 ms 256000 KB Output is correct
20 Correct 2625 ms 256000 KB Output is correct
21 Correct 655 ms 256000 KB Output is correct
22 Correct 3030 ms 256000 KB Output is correct
23 Correct 674 ms 256000 KB Output is correct
24 Correct 1756 ms 256000 KB Output is correct
25 Correct 2693 ms 256000 KB Output is correct
26 Correct 2394 ms 256000 KB Output is correct
27 Correct 2302 ms 256000 KB Output is correct
28 Correct 1211 ms 256000 KB Output is correct
29 Correct 2858 ms 256000 KB Output is correct
30 Correct 8045 ms 256000 KB Output is correct
31 Correct 7232 ms 256000 KB Output is correct
32 Correct 731 ms 256000 KB Output is correct
33 Correct 974 ms 256000 KB Output is correct
34 Correct 1746 ms 256000 KB Output is correct
35 Correct 2069 ms 256000 KB Output is correct
36 Correct 3954 ms 256000 KB Output is correct
37 Correct 3212 ms 256000 KB Output is correct
38 Correct 3085 ms 256000 KB Output is correct
39 Runtime error 7770 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -