oj.uz

Submission #122028

# Submission time Handle Problem Language Result Execution time Memory
122028 2019-06-27T11:50:59 Z yusufake Game (IOI13_game) C++
80 / 100
 7566 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)

typedef long long ll;
typedef pair < int , int > pp;
 
const int mod = 1e9 + 7;
const int x_N   = 22000 * 29;
const int y_N   = 22000 * 29 * 29;

int x_to_Y[x_N],x_L[x_N],x_R[x_N],x_id = 1;
int             y_L[y_N],y_R[y_N],y_id;
ll s[y_N]; // segment tree values are stored only for -y axis


// 0 is empty node 
// s[0] should be ineffective element
// x_to_Y[0], L[0], and R[0] should be 0
// 1 is the root of the -x axis segment tree
// x_to_Y[v] is the root of the segment tree of the interval that corresponds to node 'v' in -x axis segment tree
 
ll gcd(ll u, ll v) {
    ll r;
    while (v != 0) { r = u % v; u = v; v = r; }
    return u;
} 
 
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(y_L[v],tl,tm,ly,ry) , qry_y(y_R[v],tm+1,tr,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(x_to_Y[v], 0, mod, ly, ry);
	return gcd(qry_x(x_L[v],tl,tm,lx,rx,ly,ry) , qry_x(x_R[v],tm+1,tr,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(!y_R[v]) y_R[v] = ++y_id; up_y(y_R[v],tm+1,tr,posy,y_R[r1],y_R[r2],t); }
	else          { if(!y_L[v]) y_L[v] = ++y_id; up_y(y_L[v],tl,tm,  posy,y_L[r1],y_L[r2],t); }
	s[v] = gcd(s[ y_L[v] ] , s[ y_R[v] ]);
}
void up_x(_, int posx, int posy, ll t){
	if(tl < tr){
		if(posx > tm) { if(!x_R[v]) x_R[v] = ++x_id; up_x(x_R[v],tm+1,tr,posx,posy,t); }
		else          { if(!x_L[v]) x_L[v] = ++x_id; up_x(x_L[v],tl,tm,  posx,posy,t); }
	}
	if(!x_to_Y[v]) x_to_Y[v] = ++y_id;
	up_y(x_to_Y[v],0,mod,posy,x_to_Y[ x_L[v] ],x_to_Y[ x_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:36:29: note: in expansion of macro 'tm'
  return gcd(qry_y(y_L[v],tl,tm,ly,ry) , qry_y(y_R[v],tm+1,tr,ly,ry));
                             ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:36:54: note: in expansion of macro 'tm'
  return gcd(qry_y(y_L[v],tl,tm,ly,ry) , qry_y(y_R[v],tm+1,tr,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:41:29: note: in expansion of macro 'tm'
  return gcd(qry_x(x_L[v],tl,tm,lx,rx,ly,ry) , qry_x(x_R[v],tm+1,tr,lx,rx,ly,ry));
                             ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:41:60: note: in expansion of macro 'tm'
  return gcd(qry_x(x_L[v],tl,tm,lx,rx,ly,ry) , qry_x(x_R[v],tm+1,tr,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:49:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!y_R[v]) y_R[v] = ++y_id; up_y(y_R[v],tm+1,tr,posy,y_R[r1],y_R[r2],t); }
            ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:49:59: note: in expansion of macro 'tm'
  if(posy > tm) { if(!y_R[v]) y_R[v] = ++y_id; up_y(y_R[v],tm+1,tr,posy,y_R[r1],y_R[r2],t); }
                                                           ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:50:62: note: in expansion of macro 'tm'
  else          { if(!y_L[v]) y_L[v] = ++y_id; up_y(y_L[v],tl,tm,  posy,y_L[r1],y_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:55:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!x_R[v]) x_R[v] = ++x_id; up_x(x_R[v],tm+1,tr,posx,posy,t); }
             ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:55:60: note: in expansion of macro 'tm'
   if(posx > tm) { if(!x_R[v]) x_R[v] = ++x_id; up_x(x_R[v],tm+1,tr,posx,posy,t); }
                                                            ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:56:63: note: in expansion of macro 'tm'
   else          { if(!x_L[v]) x_L[v] = ++x_id; up_x(x_L[v],tl,tm,  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 4 ms 512 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 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 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 1157 ms 27396 KB Output is correct
5 Correct 1060 ms 27768 KB Output is correct
6 Correct 1344 ms 24680 KB Output is correct
7 Correct 1410 ms 24440 KB Output is correct
8 Correct 848 ms 15580 KB Output is correct
9 Correct 1420 ms 24696 KB Output is correct
10 Correct 1308 ms 24032 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 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 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 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1741 ms 11592 KB Output is correct
13 Correct 2555 ms 5256 KB Output is correct
14 Correct 780 ms 1232 KB Output is correct
15 Correct 2965 ms 7552 KB Output is correct
16 Correct 711 ms 12380 KB Output is correct
17 Correct 1821 ms 9144 KB Output is correct
18 Correct 2739 ms 12720 KB Output is correct
19 Correct 2413 ms 12896 KB Output is correct
20 Correct 2329 ms 12212 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 484 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 256 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 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1195 ms 27460 KB Output is correct
13 Correct 886 ms 27676 KB Output is correct
14 Correct 1340 ms 24612 KB Output is correct
15 Correct 1428 ms 24408 KB Output is correct
16 Correct 843 ms 15556 KB Output is correct
17 Correct 1476 ms 24760 KB Output is correct
18 Correct 1518 ms 24276 KB Output is correct
19 Correct 1753 ms 11692 KB Output is correct
20 Correct 2433 ms 5224 KB Output is correct
21 Correct 620 ms 1272 KB Output is correct
22 Correct 2881 ms 7544 KB Output is correct
23 Correct 658 ms 12408 KB Output is correct
24 Correct 1726 ms 9336 KB Output is correct
25 Correct 2808 ms 12612 KB Output is correct
26 Correct 2488 ms 12908 KB Output is correct
27 Correct 2404 ms 12232 KB Output is correct
28 Correct 1081 ms 125688 KB Output is correct
29 Correct 2831 ms 140964 KB Output is correct
30 Correct 7566 ms 102304 KB Output is correct
31 Correct 6758 ms 78036 KB Output is correct
32 Correct 667 ms 1272 KB Output is correct
33 Correct 919 ms 2524 KB Output is correct
34 Correct 1536 ms 138008 KB Output is correct
35 Correct 2322 ms 70416 KB Output is correct
36 Correct 4190 ms 138336 KB Output is correct
37 Correct 3550 ms 138476 KB Output is correct
38 Correct 3369 ms 137648 KB Output is correct
39 Correct 2860 ms 106396 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 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 4 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 3 ms 384 KB Output is correct
12 Correct 1147 ms 27444 KB Output is correct
13 Correct 877 ms 27572 KB Output is correct
14 Correct 1390 ms 24504 KB Output is correct
15 Correct 1324 ms 24352 KB Output is correct
16 Correct 827 ms 15456 KB Output is correct
17 Correct 1385 ms 24576 KB Output is correct
18 Correct 1197 ms 24076 KB Output is correct
19 Correct 1684 ms 11456 KB Output is correct
20 Correct 2574 ms 5012 KB Output is correct
21 Correct 617 ms 1200 KB Output is correct
22 Correct 2808 ms 7340 KB Output is correct
23 Correct 648 ms 12252 KB Output is correct
24 Correct 1860 ms 8984 KB Output is correct
25 Correct 3098 ms 12584 KB Output is correct
26 Correct 2489 ms 12748 KB Output is correct
27 Correct 2232 ms 12200 KB Output is correct
28 Correct 1297 ms 125656 KB Output is correct
29 Correct 2834 ms 140892 KB Output is correct
30 Correct 7439 ms 102024 KB Output is correct
31 Correct 6736 ms 78152 KB Output is correct
32 Correct 685 ms 1248 KB Output is correct
33 Correct 885 ms 2384 KB Output is correct
34 Correct 1464 ms 137872 KB Output is correct
35 Correct 2316 ms 70360 KB Output is correct
36 Correct 4271 ms 138312 KB Output is correct
37 Correct 3418 ms 138336 KB Output is correct
38 Correct 3417 ms 137804 KB Output is correct
39 Runtime error 1447 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -