oj.uz

Submission #122000

# Submission time Handle Problem Language Result Execution time Memory
122000 2019-06-27T10:47:58 Z yusufake Game (IOI13_game) C++
80 / 100
 7544 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 * 41;
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) {}

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 256 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 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 1142 ms 30408 KB Output is correct
5 Correct 860 ms 30200 KB Output is correct
6 Correct 1311 ms 25796 KB Output is correct
7 Correct 1363 ms 25584 KB Output is correct
8 Correct 817 ms 17108 KB Output is correct
9 Correct 1344 ms 25720 KB Output is correct
10 Correct 1299 ms 25336 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 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 5 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 1703 ms 14260 KB Output is correct
13 Correct 2537 ms 6120 KB Output is correct
14 Correct 624 ms 2224 KB Output is correct
15 Correct 2849 ms 7800 KB Output is correct
16 Correct 661 ms 12636 KB Output is correct
17 Correct 1810 ms 10076 KB Output is correct
18 Correct 3087 ms 13380 KB Output is correct
19 Correct 2698 ms 13664 KB Output is correct
20 Correct 2322 ms 12676 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 3 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 1135 ms 29532 KB Output is correct
13 Correct 819 ms 29688 KB Output is correct
14 Correct 1235 ms 25180 KB Output is correct
15 Correct 1242 ms 24992 KB Output is correct
16 Correct 775 ms 16476 KB Output is correct
17 Correct 1363 ms 25056 KB Output is correct
18 Correct 1177 ms 24468 KB Output is correct
19 Correct 1721 ms 13752 KB Output is correct
20 Correct 2482 ms 5368 KB Output is correct
21 Correct 620 ms 1548 KB Output is correct
22 Correct 2927 ms 8092 KB Output is correct
23 Correct 685 ms 12540 KB Output is correct
24 Correct 1742 ms 9972 KB Output is correct
25 Correct 2976 ms 13464 KB Output is correct
26 Correct 2662 ms 13728 KB Output is correct
27 Correct 2481 ms 12896 KB Output is correct
28 Correct 1072 ms 125996 KB Output is correct
29 Correct 2840 ms 142612 KB Output is correct
30 Correct 7544 ms 102452 KB Output is correct
31 Correct 6766 ms 78720 KB Output is correct
32 Correct 690 ms 1528 KB Output is correct
33 Correct 911 ms 2968 KB Output is correct
34 Correct 1622 ms 138372 KB Output is correct
35 Correct 2253 ms 70916 KB Output is correct
36 Correct 4253 ms 138756 KB Output is correct
37 Correct 3583 ms 138424 KB Output is correct
38 Correct 3477 ms 137984 KB Output is correct
39 Correct 3270 ms 106572 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 5 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 3 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 1100 ms 28488 KB Output is correct
13 Correct 825 ms 28664 KB Output is correct
14 Correct 1238 ms 24696 KB Output is correct
15 Correct 1371 ms 24440 KB Output is correct
16 Correct 824 ms 15480 KB Output is correct
17 Correct 1660 ms 24696 KB Output is correct
18 Correct 1213 ms 24160 KB Output is correct
19 Correct 1767 ms 12584 KB Output is correct
20 Correct 2571 ms 5252 KB Output is correct
21 Correct 619 ms 1212 KB Output is correct
22 Correct 2811 ms 7476 KB Output is correct
23 Correct 658 ms 12408 KB Output is correct
24 Correct 1805 ms 9156 KB Output is correct
25 Correct 3123 ms 12904 KB Output is correct
26 Correct 2591 ms 12892 KB Output is correct
27 Correct 2602 ms 12364 KB Output is correct
28 Correct 1073 ms 125688 KB Output is correct
29 Correct 2693 ms 141240 KB Output is correct
30 Correct 7195 ms 101992 KB Output is correct
31 Correct 6464 ms 78172 KB Output is correct
32 Correct 665 ms 1272 KB Output is correct
33 Correct 879 ms 2460 KB Output is correct
34 Correct 1461 ms 137976 KB Output is correct
35 Correct 2001 ms 70600 KB Output is correct
36 Correct 4585 ms 138436 KB Output is correct
37 Correct 3624 ms 138444 KB Output is correct
38 Correct 3527 ms 137860 KB Output is correct
39 Runtime error 1216 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -