oj.uz

Submission #122130

# Submission time Handle Problem Language Result Execution time Memory
122130 2019-06-27T16:13:41 Z yusufake Game (IOI13_game) C++
80 / 100
 7449 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;
const int x_N   = 22000 * 40;
const int y_N   = 22000 * 20 * 20;
 
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) {
    memset(s , 0 , sizeof s);
    memset(x_L , 0 , sizeof x_L);
    memset(x_R , 0 , sizeof x_R);
    memset(y_L , 0 , sizeof y_L);
    memset(y_R , 0 , sizeof y_R);
    memset(x_to_Y , 0 , sizeof x_to_Y);
}

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 113 ms 148476 KB Output is correct
2 Correct 116 ms 148548 KB Output is correct
3 Correct 115 ms 148472 KB Output is correct
4 Correct 112 ms 148472 KB Output is correct
5 Correct 112 ms 148444 KB Output is correct
6 Correct 113 ms 148444 KB Output is correct
7 Correct 119 ms 148356 KB Output is correct
8 Correct 122 ms 148472 KB Output is correct
9 Correct 113 ms 148452 KB Output is correct
10 Correct 112 ms 148344 KB Output is correct
11 Correct 116 ms 148428 KB Output is correct
12 Correct 113 ms 148372 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 148472 KB Output is correct
2 Correct 112 ms 148344 KB Output is correct
3 Correct 113 ms 148344 KB Output is correct
4 Correct 1241 ms 155080 KB Output is correct
5 Correct 922 ms 155376 KB Output is correct
6 Correct 1419 ms 152240 KB Output is correct
7 Correct 1431 ms 151692 KB Output is correct
8 Correct 954 ms 152392 KB Output is correct
9 Correct 1463 ms 151932 KB Output is correct
10 Correct 1339 ms 151412 KB Output is correct
11 Correct 114 ms 148368 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 148344 KB Output is correct
2 Correct 121 ms 148428 KB Output is correct
3 Correct 114 ms 148408 KB Output is correct
4 Correct 111 ms 148348 KB Output is correct
5 Correct 113 ms 148380 KB Output is correct
6 Correct 125 ms 148396 KB Output is correct
7 Correct 114 ms 148396 KB Output is correct
8 Correct 113 ms 148388 KB Output is correct
9 Correct 120 ms 148476 KB Output is correct
10 Correct 111 ms 148388 KB Output is correct
11 Correct 114 ms 148436 KB Output is correct
12 Correct 1778 ms 154772 KB Output is correct
13 Correct 2608 ms 151848 KB Output is correct
14 Correct 724 ms 151608 KB Output is correct
15 Correct 3027 ms 151876 KB Output is correct
16 Correct 788 ms 151732 KB Output is correct
17 Correct 1794 ms 152312 KB Output is correct
18 Correct 3030 ms 152180 KB Output is correct
19 Correct 2782 ms 152336 KB Output is correct
20 Correct 2370 ms 151648 KB Output is correct
21 Correct 113 ms 148472 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 148524 KB Output is correct
2 Correct 122 ms 148416 KB Output is correct
3 Correct 115 ms 148436 KB Output is correct
4 Correct 119 ms 148472 KB Output is correct
5 Correct 120 ms 148476 KB Output is correct
6 Correct 135 ms 148388 KB Output is correct
7 Correct 122 ms 148464 KB Output is correct
8 Correct 120 ms 148344 KB Output is correct
9 Correct 122 ms 148392 KB Output is correct
10 Correct 122 ms 148396 KB Output is correct
11 Correct 120 ms 148472 KB Output is correct
12 Correct 1262 ms 154876 KB Output is correct
13 Correct 981 ms 154976 KB Output is correct
14 Correct 1462 ms 152088 KB Output is correct
15 Correct 1468 ms 151780 KB Output is correct
16 Correct 951 ms 152588 KB Output is correct
17 Correct 1495 ms 151808 KB Output is correct
18 Correct 1389 ms 151420 KB Output is correct
19 Correct 1842 ms 154744 KB Output is correct
20 Correct 2694 ms 151760 KB Output is correct
21 Correct 763 ms 151388 KB Output is correct
22 Correct 2925 ms 151780 KB Output is correct
23 Correct 789 ms 151700 KB Output is correct
24 Correct 1835 ms 152276 KB Output is correct
25 Correct 3248 ms 152068 KB Output is correct
26 Correct 2723 ms 152156 KB Output is correct
27 Correct 2594 ms 151728 KB Output is correct
28 Correct 1113 ms 152896 KB Output is correct
29 Correct 2724 ms 155040 KB Output is correct
30 Correct 7369 ms 151516 KB Output is correct
31 Correct 7272 ms 151672 KB Output is correct
32 Correct 819 ms 152136 KB Output is correct
33 Correct 993 ms 151932 KB Output is correct
34 Correct 1479 ms 151556 KB Output is correct
35 Correct 2168 ms 152964 KB Output is correct
36 Correct 4215 ms 152720 KB Output is correct
37 Correct 3618 ms 152796 KB Output is correct
38 Correct 3675 ms 152220 KB Output is correct
39 Correct 3146 ms 152696 KB Output is correct
40 Correct 118 ms 148344 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 148456 KB Output is correct
2 Correct 123 ms 148492 KB Output is correct
3 Correct 120 ms 148344 KB Output is correct
4 Correct 120 ms 148396 KB Output is correct
5 Correct 115 ms 148488 KB Output is correct
6 Correct 118 ms 148380 KB Output is correct
7 Correct 120 ms 148384 KB Output is correct
8 Correct 113 ms 148428 KB Output is correct
9 Correct 113 ms 148444 KB Output is correct
10 Correct 117 ms 148340 KB Output is correct
11 Correct 112 ms 148372 KB Output is correct
12 Correct 1333 ms 154592 KB Output is correct
13 Correct 950 ms 154908 KB Output is correct
14 Correct 1345 ms 151540 KB Output is correct
15 Correct 1441 ms 151460 KB Output is correct
16 Correct 935 ms 152108 KB Output is correct
17 Correct 1388 ms 151564 KB Output is correct
18 Correct 1332 ms 151028 KB Output is correct
19 Correct 1789 ms 154624 KB Output is correct
20 Correct 2598 ms 151432 KB Output is correct
21 Correct 739 ms 151208 KB Output is correct
22 Correct 2996 ms 151300 KB Output is correct
23 Correct 806 ms 151416 KB Output is correct
24 Correct 1998 ms 151912 KB Output is correct
25 Correct 3096 ms 151500 KB Output is correct
26 Correct 2758 ms 152060 KB Output is correct
27 Correct 2744 ms 151468 KB Output is correct
28 Correct 1111 ms 152212 KB Output is correct
29 Correct 2746 ms 154912 KB Output is correct
30 Correct 7449 ms 151720 KB Output is correct
31 Correct 7337 ms 152052 KB Output is correct
32 Correct 833 ms 151868 KB Output is correct
33 Correct 1045 ms 151800 KB Output is correct
34 Correct 1554 ms 151868 KB Output is correct
35 Correct 2364 ms 152564 KB Output is correct
36 Correct 4514 ms 152244 KB Output is correct
37 Correct 4002 ms 152400 KB Output is correct
38 Correct 3501 ms 151956 KB Output is correct
39 Runtime error 788 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -