oj.uz

Submission #121612

# Submission time Handle Problem Language Result Execution time Memory
121612 2019-06-26T20:39:20 Z yusufake Game (IOI13_game) C++
80 / 100
 7237 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 * 53 * 53;
 
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 512 KB Output is correct
3 Correct 3 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 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 4 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 3 ms 384 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 356 KB Output is correct
4 Correct 1108 ms 27380 KB Output is correct
5 Correct 837 ms 27600 KB Output is correct
6 Correct 1245 ms 24572 KB Output is correct
7 Correct 1293 ms 24296 KB Output is correct
8 Correct 803 ms 15636 KB Output is correct
9 Correct 1307 ms 24564 KB Output is correct
10 Correct 1135 ms 24244 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 2 ms 384 KB Output is correct
2 Correct 3 ms 512 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 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 384 KB Output is correct
12 Correct 1662 ms 12572 KB Output is correct
13 Correct 2492 ms 6144 KB Output is correct
14 Correct 621 ms 1224 KB Output is correct
15 Correct 2840 ms 8976 KB Output is correct
16 Correct 670 ms 14700 KB Output is correct
17 Correct 1746 ms 10816 KB Output is correct
18 Correct 2829 ms 14972 KB Output is correct
19 Correct 2535 ms 14976 KB Output is correct
20 Correct 2338 ms 14508 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 512 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 4 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 380 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 384 KB Output is correct
12 Correct 1132 ms 27352 KB Output is correct
13 Correct 850 ms 27604 KB Output is correct
14 Correct 1319 ms 24524 KB Output is correct
15 Correct 1282 ms 24184 KB Output is correct
16 Correct 826 ms 15396 KB Output is correct
17 Correct 1350 ms 24468 KB Output is correct
18 Correct 1174 ms 24092 KB Output is correct
19 Correct 1662 ms 12568 KB Output is correct
20 Correct 2586 ms 6092 KB Output is correct
21 Correct 620 ms 1024 KB Output is correct
22 Correct 3107 ms 8908 KB Output is correct
23 Correct 681 ms 14492 KB Output is correct
24 Correct 1800 ms 10820 KB Output is correct
25 Correct 3060 ms 14864 KB Output is correct
26 Correct 2450 ms 15060 KB Output is correct
27 Correct 2299 ms 14524 KB Output is correct
28 Correct 1128 ms 157636 KB Output is correct
29 Correct 2833 ms 175836 KB Output is correct
30 Correct 7219 ms 119984 KB Output is correct
31 Correct 6700 ms 91696 KB Output is correct
32 Correct 686 ms 1208 KB Output is correct
33 Correct 928 ms 2676 KB Output is correct
34 Correct 1529 ms 172860 KB Output is correct
35 Correct 2170 ms 87984 KB Output is correct
36 Correct 4190 ms 173260 KB Output is correct
37 Correct 3388 ms 173388 KB Output is correct
38 Correct 3382 ms 172832 KB Output is correct
39 Correct 2876 ms 133188 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 2 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 596 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 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1117 ms 27352 KB Output is correct
13 Correct 838 ms 27604 KB Output is correct
14 Correct 1338 ms 24508 KB Output is correct
15 Correct 1305 ms 24220 KB Output is correct
16 Correct 780 ms 15540 KB Output is correct
17 Correct 1293 ms 24556 KB Output is correct
18 Correct 1189 ms 24040 KB Output is correct
19 Correct 1640 ms 12552 KB Output is correct
20 Correct 2585 ms 6184 KB Output is correct
21 Correct 614 ms 1144 KB Output is correct
22 Correct 3119 ms 8916 KB Output is correct
23 Correct 754 ms 14556 KB Output is correct
24 Correct 1645 ms 10696 KB Output is correct
25 Correct 2755 ms 14900 KB Output is correct
26 Correct 2452 ms 15108 KB Output is correct
27 Correct 2272 ms 14512 KB Output is correct
28 Correct 1135 ms 157644 KB Output is correct
29 Correct 2887 ms 175756 KB Output is correct
30 Correct 7237 ms 120108 KB Output is correct
31 Correct 6614 ms 91868 KB Output is correct
32 Correct 690 ms 1328 KB Output is correct
33 Correct 920 ms 2836 KB Output is correct
34 Correct 1540 ms 172888 KB Output is correct
35 Correct 2273 ms 88092 KB Output is correct
36 Correct 4120 ms 173380 KB Output is correct
37 Correct 3470 ms 173480 KB Output is correct
38 Correct 3415 ms 172740 KB Output is correct
39 Runtime error 1140 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -