oj.uz

Submission #42767

# Submission time Handle Problem Language Result Execution time Memory
42767 2018-03-03T22:29:58 Z yusufake Game (IOI13_game) C++
80 / 100
 7997 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 * 400;
 
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 380 KB Output is correct
2 Correct 4 ms 608 KB Output is correct
3 Correct 5 ms 680 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 4 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 2 ms 752 KB Output is correct
9 Correct 3 ms 752 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 2 ms 752 KB Output is correct
12 Correct 1 ms 752 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 752 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 752 KB Output is correct
4 Correct 1163 ms 30468 KB Output is correct
5 Correct 1002 ms 34716 KB Output is correct
6 Correct 1397 ms 36360 KB Output is correct
7 Correct 1434 ms 40736 KB Output is correct
8 Correct 847 ms 40736 KB Output is correct
9 Correct 1405 ms 49868 KB Output is correct
10 Correct 1197 ms 53884 KB Output is correct
11 Correct 2 ms 53884 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 53884 KB Output is correct
2 Correct 4 ms 53884 KB Output is correct
3 Correct 4 ms 53884 KB Output is correct
4 Correct 2 ms 53884 KB Output is correct
5 Correct 2 ms 53884 KB Output is correct
6 Correct 3 ms 53884 KB Output is correct
7 Correct 2 ms 53884 KB Output is correct
8 Correct 2 ms 53884 KB Output is correct
9 Correct 3 ms 53884 KB Output is correct
10 Correct 2 ms 53884 KB Output is correct
11 Correct 2 ms 53884 KB Output is correct
12 Correct 1698 ms 53884 KB Output is correct
13 Correct 2728 ms 53884 KB Output is correct
14 Correct 681 ms 53884 KB Output is correct
15 Correct 3176 ms 53884 KB Output is correct
16 Correct 706 ms 53884 KB Output is correct
17 Correct 1783 ms 53884 KB Output is correct
18 Correct 2720 ms 58584 KB Output is correct
19 Correct 2478 ms 64100 KB Output is correct
20 Correct 2265 ms 68996 KB Output is correct
21 Correct 2 ms 68996 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 68996 KB Output is correct
2 Correct 4 ms 68996 KB Output is correct
3 Correct 4 ms 68996 KB Output is correct
4 Correct 2 ms 68996 KB Output is correct
5 Correct 3 ms 68996 KB Output is correct
6 Correct 4 ms 68996 KB Output is correct
7 Correct 2 ms 68996 KB Output is correct
8 Correct 2 ms 68996 KB Output is correct
9 Correct 3 ms 68996 KB Output is correct
10 Correct 3 ms 68996 KB Output is correct
11 Correct 2 ms 68996 KB Output is correct
12 Correct 1186 ms 84752 KB Output is correct
13 Correct 907 ms 88664 KB Output is correct
14 Correct 1339 ms 90436 KB Output is correct
15 Correct 1355 ms 94808 KB Output is correct
16 Correct 839 ms 94808 KB Output is correct
17 Correct 1310 ms 103848 KB Output is correct
18 Correct 1252 ms 108096 KB Output is correct
19 Correct 1669 ms 108096 KB Output is correct
20 Correct 2717 ms 108096 KB Output is correct
21 Correct 676 ms 108096 KB Output is correct
22 Correct 3161 ms 110116 KB Output is correct
23 Correct 678 ms 120072 KB Output is correct
24 Correct 1692 ms 121232 KB Output is correct
25 Correct 2763 ms 130440 KB Output is correct
26 Correct 2380 ms 135908 KB Output is correct
27 Correct 2173 ms 140828 KB Output is correct
28 Correct 1164 ms 256000 KB Output is correct
29 Correct 2901 ms 256000 KB Output is correct
30 Correct 7997 ms 256000 KB Output is correct
31 Correct 7216 ms 256000 KB Output is correct
32 Correct 758 ms 256000 KB Output is correct
33 Correct 1000 ms 256000 KB Output is correct
34 Correct 1787 ms 256000 KB Output is correct
35 Correct 2115 ms 256000 KB Output is correct
36 Correct 3979 ms 256000 KB Output is correct
37 Correct 3227 ms 256000 KB Output is correct
38 Correct 3219 ms 256000 KB Output is correct
39 Correct 2687 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 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 3 ms 256000 KB Output is correct
11 Correct 2 ms 256000 KB Output is correct
12 Correct 1120 ms 256000 KB Output is correct
13 Correct 852 ms 256000 KB Output is correct
14 Correct 1286 ms 256000 KB Output is correct
15 Correct 1281 ms 256000 KB Output is correct
16 Correct 800 ms 256000 KB Output is correct
17 Correct 1320 ms 256000 KB Output is correct
18 Correct 1190 ms 256000 KB Output is correct
19 Correct 1651 ms 256000 KB Output is correct
20 Correct 2701 ms 256000 KB Output is correct
21 Correct 687 ms 256000 KB Output is correct
22 Correct 3129 ms 256000 KB Output is correct
23 Correct 728 ms 256000 KB Output is correct
24 Correct 1694 ms 256000 KB Output is correct
25 Correct 2706 ms 256000 KB Output is correct
26 Correct 2464 ms 256000 KB Output is correct
27 Correct 2223 ms 256000 KB Output is correct
28 Correct 1204 ms 256000 KB Output is correct
29 Correct 2929 ms 256000 KB Output is correct
30 Correct 7908 ms 256000 KB Output is correct
31 Correct 7231 ms 256000 KB Output is correct
32 Correct 749 ms 256000 KB Output is correct
33 Correct 1026 ms 256000 KB Output is correct
34 Correct 1728 ms 256000 KB Output is correct
35 Correct 2169 ms 256000 KB Output is correct
36 Correct 3879 ms 256000 KB Output is correct
37 Correct 3201 ms 256000 KB Output is correct
38 Correct 2987 ms 256000 KB Output is correct
39 Runtime error 4504 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -