oj.uz

Submission #121986

# Submission time Handle Problem Language Result Execution time Memory
121986 2019-06-27T10:26:43 Z yusufake Game (IOI13_game) C++
80 / 100
 13000 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)
#define sol L[v],tl,tm
#define sag R[v],tm+1,tr
 
#define mp make_pair
#define pb push_back
#define st first
#define nd second
 
typedef long long ll;
typedef pair < int , int > pp;
 
const int mod = 1e9 + 7;
const int N   = 22000 * 27 * 27;

int L[N],R[N],id;
ll s[N];


// 0 is empty node 
// s[0] should be ineffective element
// Y[0], L[0], and R[0] should be 0
// 1 is the root of the -x axis segment tree
// 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(sol,ly,ry) , qry_y(sag,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(s[v], 0, mod, ly, ry);
	return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
}
 
void up_y(_, int posy, int r1, int r2, ll t){  
    if(id == N - 5) while(1);
    if(tl == tr){
		s[v] = t == -1 ? gcd(s[r1] , s[r2]) : t;
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,posy,L[r1],L[r2],t); }
	s[v] = gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_, int posx, int posy, ll t){
    if(id == N - 5) while(1);
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
		else          { if(!L[v]) L[v] = ++id; up_x(sol,posx,posy,t); }
	}
	if(!s[v]) s[v] = ++id;
	up_y(s[v],0,mod,posy,s[ L[v] ],s[ 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(Y , 0 , sizeof Y);
    memset(L , 0 , sizeof L);
    memset(R , 0 , sizeof R);
    id = 1;
}

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:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^~
game.cpp:41:19: note: in expansion of macro 'sol'
  return gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
                   ^~~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^~
game.cpp:41:38: note: in expansion of macro 'sag'
  return gcd(qry_y(sol,ly,ry) , qry_y(sag,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:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^~
game.cpp:46:19: note: in expansion of macro 'sol'
  return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
                   ^~~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^~
game.cpp:46:44: note: in expansion of macro 'sag'
  return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,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:55:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
            ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^~
game.cpp:55:46: note: in expansion of macro 'sag'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
                                              ^~~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^~
game.cpp:56:46: note: in expansion of macro 'sol'
  else          { if(!L[v]) L[v] = ++id; up_y(sol,posy,L[r1],L[r2],t); }
                                              ^~~
game.cpp: In function 'void up_x(int, int, int, int, int, ll)':
game.cpp:60:21: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     if(id == N - 5) while(1);
                     ^~~~~
game.cpp:61:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  if(tl < tr){
  ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:62:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
             ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^~
game.cpp:62:47: note: in expansion of macro 'sag'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
                                               ^~~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^~
game.cpp:63:47: note: in expansion of macro 'sol'
   else          { if(!L[v]) L[v] = ++id; up_x(sol,posx,posy,t); }
                                               ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 251432 KB Output is correct
2 Correct 188 ms 251516 KB Output is correct
3 Correct 192 ms 251384 KB Output is correct
4 Correct 193 ms 251388 KB Output is correct
5 Correct 206 ms 251384 KB Output is correct
6 Correct 191 ms 251388 KB Output is correct
7 Correct 198 ms 251332 KB Output is correct
8 Correct 188 ms 251384 KB Output is correct
9 Correct 191 ms 251420 KB Output is correct
10 Correct 186 ms 251324 KB Output is correct
11 Correct 196 ms 251364 KB Output is correct
12 Correct 192 ms 251384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 251428 KB Output is correct
2 Correct 190 ms 251392 KB Output is correct
3 Correct 192 ms 251384 KB Output is correct
4 Correct 1346 ms 256000 KB Output is correct
5 Correct 1025 ms 256000 KB Output is correct
6 Correct 1474 ms 255948 KB Output is correct
7 Correct 1533 ms 255640 KB Output is correct
8 Correct 940 ms 256000 KB Output is correct
9 Correct 1464 ms 255836 KB Output is correct
10 Correct 1387 ms 255464 KB Output is correct
11 Correct 196 ms 251480 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 251436 KB Output is correct
2 Correct 191 ms 251440 KB Output is correct
3 Correct 194 ms 251408 KB Output is correct
4 Correct 185 ms 251384 KB Output is correct
5 Correct 191 ms 251388 KB Output is correct
6 Correct 195 ms 251384 KB Output is correct
7 Correct 184 ms 251368 KB Output is correct
8 Correct 186 ms 251384 KB Output is correct
9 Correct 192 ms 251432 KB Output is correct
10 Correct 202 ms 251356 KB Output is correct
11 Correct 198 ms 251324 KB Output is correct
12 Correct 1918 ms 256000 KB Output is correct
13 Correct 2812 ms 255740 KB Output is correct
14 Correct 802 ms 255460 KB Output is correct
15 Correct 2996 ms 255952 KB Output is correct
16 Correct 863 ms 255952 KB Output is correct
17 Correct 2035 ms 256000 KB Output is correct
18 Correct 3128 ms 256000 KB Output is correct
19 Correct 2788 ms 256000 KB Output is correct
20 Correct 2550 ms 255912 KB Output is correct
21 Correct 194 ms 251356 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 251416 KB Output is correct
2 Correct 199 ms 251356 KB Output is correct
3 Correct 196 ms 251384 KB Output is correct
4 Correct 193 ms 251336 KB Output is correct
5 Correct 186 ms 251340 KB Output is correct
6 Correct 181 ms 251384 KB Output is correct
7 Correct 183 ms 251440 KB Output is correct
8 Correct 186 ms 251384 KB Output is correct
9 Correct 183 ms 251384 KB Output is correct
10 Correct 181 ms 251384 KB Output is correct
11 Correct 184 ms 251384 KB Output is correct
12 Correct 1270 ms 256000 KB Output is correct
13 Correct 1025 ms 256000 KB Output is correct
14 Correct 1440 ms 256000 KB Output is correct
15 Correct 1546 ms 256000 KB Output is correct
16 Correct 983 ms 256000 KB Output is correct
17 Correct 1489 ms 256000 KB Output is correct
18 Correct 1412 ms 255684 KB Output is correct
19 Correct 1879 ms 256000 KB Output is correct
20 Correct 2637 ms 255968 KB Output is correct
21 Correct 831 ms 255768 KB Output is correct
22 Correct 3179 ms 256000 KB Output is correct
23 Correct 868 ms 255924 KB Output is correct
24 Correct 2035 ms 256000 KB Output is correct
25 Correct 3288 ms 256000 KB Output is correct
26 Correct 2914 ms 256000 KB Output is correct
27 Correct 2706 ms 255768 KB Output is correct
28 Correct 1173 ms 254840 KB Output is correct
29 Correct 2994 ms 256000 KB Output is correct
30 Correct 7524 ms 254968 KB Output is correct
31 Correct 6879 ms 255016 KB Output is correct
32 Correct 858 ms 254708 KB Output is correct
33 Correct 1098 ms 254540 KB Output is correct
34 Correct 1587 ms 254932 KB Output is correct
35 Correct 2346 ms 255276 KB Output is correct
36 Correct 4536 ms 254980 KB Output is correct
37 Correct 3396 ms 255248 KB Output is correct
38 Correct 3293 ms 254860 KB Output is correct
39 Correct 2877 ms 254080 KB Output is correct
40 Correct 188 ms 251464 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 251524 KB Output is correct
2 Correct 195 ms 251416 KB Output is correct
3 Correct 203 ms 251384 KB Output is correct
4 Correct 190 ms 251384 KB Output is correct
5 Correct 187 ms 251352 KB Output is correct
6 Correct 190 ms 251412 KB Output is correct
7 Correct 197 ms 251508 KB Output is correct
8 Correct 194 ms 251444 KB Output is correct
9 Correct 198 ms 251384 KB Output is correct
10 Correct 191 ms 251384 KB Output is correct
11 Correct 199 ms 251512 KB Output is correct
12 Correct 1388 ms 256000 KB Output is correct
13 Correct 1071 ms 256000 KB Output is correct
14 Correct 1500 ms 253816 KB Output is correct
15 Correct 1531 ms 253660 KB Output is correct
16 Correct 1047 ms 254472 KB Output is correct
17 Correct 1505 ms 253784 KB Output is correct
18 Correct 1331 ms 253236 KB Output is correct
19 Correct 1837 ms 256000 KB Output is correct
20 Correct 2626 ms 253684 KB Output is correct
21 Correct 832 ms 253296 KB Output is correct
22 Correct 3148 ms 253444 KB Output is correct
23 Correct 894 ms 253436 KB Output is correct
24 Correct 2049 ms 254200 KB Output is correct
25 Correct 3383 ms 253952 KB Output is correct
26 Correct 2886 ms 253960 KB Output is correct
27 Correct 2638 ms 253388 KB Output is correct
28 Correct 1174 ms 253228 KB Output is correct
29 Correct 3013 ms 256000 KB Output is correct
30 Correct 7863 ms 253048 KB Output is correct
31 Correct 7066 ms 252800 KB Output is correct
32 Correct 895 ms 252420 KB Output is correct
33 Correct 1155 ms 252664 KB Output is correct
34 Correct 1690 ms 252760 KB Output is correct
35 Correct 2564 ms 253360 KB Output is correct
36 Correct 4493 ms 252964 KB Output is correct
37 Correct 3469 ms 253164 KB Output is correct
38 Correct 3520 ms 252792 KB Output is correct
39 Execution timed out 13051 ms 256000 KB Time limit exceeded
40 Halted 0 ms 0 KB -