oj.uz

Submission #122033

# Submission time Handle Problem Language Result Execution time Memory
122033 2019-06-27T11:59:51 Z yusufake Game (IOI13_game) C++
80 / 100
 7320 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 * 23;
const int y_N   = 22000 * 23 * 23;

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 145 ms 188536 KB Output is correct
2 Correct 146 ms 188536 KB Output is correct
3 Correct 145 ms 188536 KB Output is correct
4 Correct 140 ms 188504 KB Output is correct
5 Correct 142 ms 188452 KB Output is correct
6 Correct 140 ms 188452 KB Output is correct
7 Correct 140 ms 188536 KB Output is correct
8 Correct 143 ms 188408 KB Output is correct
9 Correct 139 ms 188488 KB Output is correct
10 Correct 137 ms 188536 KB Output is correct
11 Correct 138 ms 188508 KB Output is correct
12 Correct 137 ms 188536 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 188488 KB Output is correct
2 Correct 143 ms 188424 KB Output is correct
3 Correct 140 ms 188508 KB Output is correct
4 Correct 1275 ms 192536 KB Output is correct
5 Correct 982 ms 192896 KB Output is correct
6 Correct 1385 ms 189828 KB Output is correct
7 Correct 1692 ms 189640 KB Output is correct
8 Correct 1008 ms 190164 KB Output is correct
9 Correct 1535 ms 189548 KB Output is correct
10 Correct 1347 ms 189108 KB Output is correct
11 Correct 141 ms 188536 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 188476 KB Output is correct
2 Correct 137 ms 188488 KB Output is correct
3 Correct 139 ms 188440 KB Output is correct
4 Correct 137 ms 188536 KB Output is correct
5 Correct 141 ms 188408 KB Output is correct
6 Correct 140 ms 188568 KB Output is correct
7 Correct 138 ms 188480 KB Output is correct
8 Correct 146 ms 188536 KB Output is correct
9 Correct 142 ms 188412 KB Output is correct
10 Correct 138 ms 188524 KB Output is correct
11 Correct 137 ms 188536 KB Output is correct
12 Correct 1869 ms 192720 KB Output is correct
13 Correct 2616 ms 189540 KB Output is correct
14 Correct 754 ms 189176 KB Output is correct
15 Correct 2958 ms 189424 KB Output is correct
16 Correct 792 ms 189448 KB Output is correct
17 Correct 2004 ms 190048 KB Output is correct
18 Correct 3174 ms 189696 KB Output is correct
19 Correct 2665 ms 189836 KB Output is correct
20 Correct 2741 ms 189204 KB Output is correct
21 Correct 142 ms 188408 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 188408 KB Output is correct
2 Correct 145 ms 188408 KB Output is correct
3 Correct 144 ms 188408 KB Output is correct
4 Correct 138 ms 188476 KB Output is correct
5 Correct 153 ms 188488 KB Output is correct
6 Correct 278 ms 188448 KB Output is correct
7 Correct 142 ms 188536 KB Output is correct
8 Correct 145 ms 188420 KB Output is correct
9 Correct 147 ms 188536 KB Output is correct
10 Correct 136 ms 188536 KB Output is correct
11 Correct 138 ms 188536 KB Output is correct
12 Correct 1212 ms 192528 KB Output is correct
13 Correct 1020 ms 193008 KB Output is correct
14 Correct 1474 ms 189736 KB Output is correct
15 Correct 1501 ms 189432 KB Output is correct
16 Correct 986 ms 190248 KB Output is correct
17 Correct 1778 ms 189468 KB Output is correct
18 Correct 1404 ms 189232 KB Output is correct
19 Correct 1847 ms 192624 KB Output is correct
20 Correct 2615 ms 189364 KB Output is correct
21 Correct 762 ms 189108 KB Output is correct
22 Correct 3082 ms 189368 KB Output is correct
23 Correct 823 ms 189300 KB Output is correct
24 Correct 2031 ms 189888 KB Output is correct
25 Correct 3217 ms 189804 KB Output is correct
26 Correct 2683 ms 189708 KB Output is correct
27 Correct 2692 ms 189180 KB Output is correct
28 Correct 1238 ms 189128 KB Output is correct
29 Correct 2886 ms 192320 KB Output is correct
30 Correct 7320 ms 189116 KB Output is correct
31 Correct 6861 ms 189408 KB Output is correct
32 Correct 835 ms 189048 KB Output is correct
33 Correct 1061 ms 189020 KB Output is correct
34 Correct 1544 ms 189304 KB Output is correct
35 Correct 2335 ms 189984 KB Output is correct
36 Correct 4794 ms 189476 KB Output is correct
37 Correct 3591 ms 189768 KB Output is correct
38 Correct 3376 ms 189312 KB Output is correct
39 Correct 2922 ms 189892 KB Output is correct
40 Correct 142 ms 188408 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 188508 KB Output is correct
2 Correct 138 ms 188436 KB Output is correct
3 Correct 139 ms 188408 KB Output is correct
4 Correct 150 ms 188408 KB Output is correct
5 Correct 138 ms 188500 KB Output is correct
6 Correct 143 ms 188508 KB Output is correct
7 Correct 142 ms 188584 KB Output is correct
8 Correct 146 ms 188508 KB Output is correct
9 Correct 143 ms 188536 KB Output is correct
10 Correct 140 ms 188480 KB Output is correct
11 Correct 141 ms 188408 KB Output is correct
12 Correct 1217 ms 192520 KB Output is correct
13 Correct 994 ms 192792 KB Output is correct
14 Correct 1346 ms 189604 KB Output is correct
15 Correct 1371 ms 189516 KB Output is correct
16 Correct 983 ms 190072 KB Output is correct
17 Correct 1460 ms 189560 KB Output is correct
18 Correct 1336 ms 189056 KB Output is correct
19 Correct 1873 ms 192504 KB Output is correct
20 Correct 2751 ms 189264 KB Output is correct
21 Correct 775 ms 189184 KB Output is correct
22 Correct 3064 ms 189336 KB Output is correct
23 Correct 811 ms 189304 KB Output is correct
24 Correct 1988 ms 189816 KB Output is correct
25 Correct 3362 ms 189824 KB Output is correct
26 Correct 2828 ms 189816 KB Output is correct
27 Correct 2526 ms 189112 KB Output is correct
28 Correct 1116 ms 189176 KB Output is correct
29 Correct 2924 ms 192172 KB Output is correct
30 Correct 7234 ms 189124 KB Output is correct
31 Correct 6868 ms 189612 KB Output is correct
32 Correct 856 ms 189380 KB Output is correct
33 Correct 1073 ms 189264 KB Output is correct
34 Correct 1541 ms 189432 KB Output is correct
35 Correct 2346 ms 190124 KB Output is correct
36 Correct 4595 ms 189884 KB Output is correct
37 Correct 3531 ms 190004 KB Output is correct
38 Correct 3511 ms 189500 KB Output is correct
39 Runtime error 1165 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -