oj.uz

Submission #121598

# Submission time Handle Problem Language Result Execution time Memory
121598 2019-06-26T20:22:42 Z yusufake Game (IOI13_game) C++
80 / 100
 7341 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 * 30 * 30;
 
int Y[N],L[N],R[N],id=1;
ll s[N];
 
// 0 is empty node 
// s[0] should be ineffective element
// L[0] and R[0] should be 0
// 1 is the root of the -x axis segment tree
// Y[v] is the root of the segment tree of the interval that corresponds to node 'v' in -x axis segment tree
 
ll qry_y(_, int ly, int ry) { 
	if(ly > tr || ry < tl || !v) return 0;
	if (ly <= tl && tr <= ry) return s[v];
	return __gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
}
ll qry_x(_, int lx, int rx, int ly, int ry) { 
	if(lx > tr || rx < tl) return 0;
	if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod, ly, ry);
	return __gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
}
 
void up_y(_, int posy, int r1, int r2, ll t){  
    if(tl == tr){
		s[v] = t == -1 ? __gcd(s[r1] , s[r2]) : t;
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,posy,L[r1],L[r2],t); }
	s[v] = __gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_, int posx, int posy, ll t){
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
		else          { if(!L[v]) L[v] = ++id; up_x(sol,posx,posy,t); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,posy,Y[ L[v] ],Y[ R[v] ],(tl==tr?t:-1));
}
 
 
void update(int posx, int posy, ll t){
	up_x(1,0,mod,posx,posy,t);
}	

ll calculate(int lx, int ly, int rx, int ry){
	return qry_x(1,0,mod,lx,rx,ly,ry);
}	
 
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, 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:21: note: in expansion of macro 'sol'
  return __gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
                     ^~~
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:40: note: in expansion of macro 'sag'
  return __gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
                                        ^~~
game.cpp: In function 'll qry_x(int, int, int, int, 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:21: note: in expansion of macro 'sol'
  return __gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
                     ^~~
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:46: note: in expansion of macro 'sag'
  return __gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
                                              ^~~
game.cpp: In function 'void up_y(int, int, int, int, int, int, ll)':
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,posy,R[r1],R[r2],t); }
            ^~
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,posy,R[r1],R[r2],t); }
                                              ^~~
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,posy,L[r1],L[r2],t); }
                                              ^~~
game.cpp: In function 'void up_x(int, int, int, int, int, ll)':
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,posx,posy,t); }
             ^~
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,posx,posy,t); }
                                               ^~~
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,posx,posy,t); }
                                               ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1101 ms 27924 KB Output is correct
5 Correct 836 ms 28340 KB Output is correct
6 Correct 1236 ms 25336 KB Output is correct
7 Correct 1238 ms 25144 KB Output is correct
8 Correct 794 ms 16252 KB Output is correct
9 Correct 1310 ms 25264 KB Output is correct
10 Correct 1225 ms 24724 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1699 ms 13244 KB Output is correct
13 Correct 2494 ms 6896 KB Output is correct
14 Correct 646 ms 1980 KB Output is correct
15 Correct 2886 ms 9680 KB Output is correct
16 Correct 674 ms 15352 KB Output is correct
17 Correct 1779 ms 11464 KB Output is correct
18 Correct 2785 ms 15632 KB Output is correct
19 Correct 2424 ms 15588 KB Output is correct
20 Correct 2438 ms 15196 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1093 ms 28204 KB Output is correct
13 Correct 856 ms 28232 KB Output is correct
14 Correct 1400 ms 25388 KB Output is correct
15 Correct 1327 ms 25240 KB Output is correct
16 Correct 889 ms 16216 KB Output is correct
17 Correct 1310 ms 25300 KB Output is correct
18 Correct 1167 ms 24780 KB Output is correct
19 Correct 1690 ms 13368 KB Output is correct
20 Correct 2529 ms 6796 KB Output is correct
21 Correct 627 ms 2040 KB Output is correct
22 Correct 2859 ms 9740 KB Output is correct
23 Correct 658 ms 15416 KB Output is correct
24 Correct 1648 ms 11584 KB Output is correct
25 Correct 2738 ms 15752 KB Output is correct
26 Correct 2498 ms 15680 KB Output is correct
27 Correct 2322 ms 15332 KB Output is correct
28 Correct 1251 ms 158456 KB Output is correct
29 Correct 2887 ms 176636 KB Output is correct
30 Correct 7341 ms 120452 KB Output is correct
31 Correct 6864 ms 92508 KB Output is correct
32 Correct 685 ms 2012 KB Output is correct
33 Correct 918 ms 3712 KB Output is correct
34 Correct 1555 ms 173768 KB Output is correct
35 Correct 2261 ms 88844 KB Output is correct
36 Correct 4091 ms 174312 KB Output is correct
37 Correct 3344 ms 174324 KB Output is correct
38 Correct 3489 ms 173724 KB Output is correct
39 Correct 2716 ms 134040 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1082 ms 28100 KB Output is correct
13 Correct 818 ms 28296 KB Output is correct
14 Correct 1296 ms 25420 KB Output is correct
15 Correct 1288 ms 25096 KB Output is correct
16 Correct 809 ms 16264 KB Output is correct
17 Correct 1287 ms 25432 KB Output is correct
18 Correct 1206 ms 24764 KB Output is correct
19 Correct 1680 ms 13592 KB Output is correct
20 Correct 2497 ms 6844 KB Output is correct
21 Correct 614 ms 2040 KB Output is correct
22 Correct 2861 ms 9844 KB Output is correct
23 Correct 677 ms 15352 KB Output is correct
24 Correct 1779 ms 11540 KB Output is correct
25 Correct 2989 ms 15692 KB Output is correct
26 Correct 2531 ms 15840 KB Output is correct
27 Correct 2420 ms 15260 KB Output is correct
28 Correct 1226 ms 158456 KB Output is correct
29 Correct 3214 ms 176644 KB Output is correct
30 Correct 7338 ms 120428 KB Output is correct
31 Correct 6758 ms 92528 KB Output is correct
32 Correct 682 ms 1884 KB Output is correct
33 Correct 933 ms 3464 KB Output is correct
34 Correct 1549 ms 173608 KB Output is correct
35 Correct 2243 ms 88564 KB Output is correct
36 Correct 4235 ms 174068 KB Output is correct
37 Correct 3371 ms 174064 KB Output is correct
38 Correct 3318 ms 173316 KB Output is correct
39 Runtime error 1142 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -