oj.uz

Submission #122030

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

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 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 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 384 KB Output is correct
4 Correct 1097 ms 27256 KB Output is correct
5 Correct 834 ms 27432 KB Output is correct
6 Correct 1250 ms 24528 KB Output is correct
7 Correct 1336 ms 24340 KB Output is correct
8 Correct 845 ms 15460 KB Output is correct
9 Correct 1379 ms 24504 KB Output is correct
10 Correct 1263 ms 23948 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 356 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 1761 ms 11472 KB Output is correct
13 Correct 2547 ms 5060 KB Output is correct
14 Correct 625 ms 1064 KB Output is correct
15 Correct 2945 ms 7448 KB Output is correct
16 Correct 697 ms 12288 KB Output is correct
17 Correct 1852 ms 9012 KB Output is correct
18 Correct 3013 ms 12732 KB Output is correct
19 Correct 2691 ms 12728 KB Output is correct
20 Correct 2326 ms 12096 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 560 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 1179 ms 27352 KB Output is correct
13 Correct 880 ms 27452 KB Output is correct
14 Correct 1367 ms 24512 KB Output is correct
15 Correct 1370 ms 24196 KB Output is correct
16 Correct 815 ms 15432 KB Output is correct
17 Correct 1312 ms 24492 KB Output is correct
18 Correct 1199 ms 24032 KB Output is correct
19 Correct 1692 ms 11612 KB Output is correct
20 Correct 2640 ms 5244 KB Output is correct
21 Correct 665 ms 1016 KB Output is correct
22 Correct 2960 ms 7412 KB Output is correct
23 Correct 697 ms 12324 KB Output is correct
24 Correct 1786 ms 9040 KB Output is correct
25 Correct 2937 ms 12568 KB Output is correct
26 Correct 2935 ms 12660 KB Output is correct
27 Correct 2314 ms 12140 KB Output is correct
28 Correct 1076 ms 125540 KB Output is correct
29 Correct 2637 ms 140780 KB Output is correct
30 Correct 7365 ms 102024 KB Output is correct
31 Correct 6629 ms 78184 KB Output is correct
32 Correct 673 ms 1100 KB Output is correct
33 Correct 898 ms 2440 KB Output is correct
34 Correct 1531 ms 137992 KB Output is correct
35 Correct 2186 ms 70524 KB Output is correct
36 Correct 4091 ms 138452 KB Output is correct
37 Correct 3592 ms 138452 KB Output is correct
38 Correct 3570 ms 138044 KB Output is correct
39 Correct 3168 ms 106364 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 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 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1091 ms 27640 KB Output is correct
13 Correct 839 ms 27512 KB Output is correct
14 Correct 1243 ms 24560 KB Output is correct
15 Correct 1228 ms 24388 KB Output is correct
16 Correct 773 ms 15608 KB Output is correct
17 Correct 1292 ms 24700 KB Output is correct
18 Correct 1223 ms 24160 KB Output is correct
19 Correct 1630 ms 11644 KB Output is correct
20 Correct 2485 ms 5200 KB Output is correct
21 Correct 614 ms 1088 KB Output is correct
22 Correct 2832 ms 7464 KB Output is correct
23 Correct 697 ms 12408 KB Output is correct
24 Correct 1852 ms 9156 KB Output is correct
25 Correct 2858 ms 12884 KB Output is correct
26 Correct 2950 ms 12864 KB Output is correct
27 Correct 2466 ms 12260 KB Output is correct
28 Correct 1077 ms 125704 KB Output is correct
29 Correct 2724 ms 140988 KB Output is correct
30 Correct 7260 ms 102180 KB Output is correct
31 Correct 6820 ms 78256 KB Output is correct
32 Correct 678 ms 1272 KB Output is correct
33 Correct 895 ms 2572 KB Output is correct
34 Correct 1501 ms 138088 KB Output is correct
35 Correct 2305 ms 70568 KB Output is correct
36 Correct 4428 ms 138328 KB Output is correct
37 Correct 3663 ms 138364 KB Output is correct
38 Correct 3366 ms 137724 KB Output is correct
39 Runtime error 1411 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -