oj.uz

Submission #121983

# Submission time Handle Problem Language Result Execution time Memory
121983 2019-06-27T10:24:30 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 191 ms 251384 KB Output is correct
2 Correct 192 ms 251460 KB Output is correct
3 Correct 210 ms 251436 KB Output is correct
4 Correct 184 ms 251440 KB Output is correct
5 Correct 181 ms 251416 KB Output is correct
6 Correct 213 ms 251448 KB Output is correct
7 Correct 209 ms 251384 KB Output is correct
8 Correct 189 ms 251556 KB Output is correct
9 Correct 189 ms 251376 KB Output is correct
10 Correct 197 ms 251384 KB Output is correct
11 Correct 186 ms 251512 KB Output is correct
12 Correct 184 ms 251380 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 251508 KB Output is correct
2 Correct 183 ms 251336 KB Output is correct
3 Correct 181 ms 251348 KB Output is correct
4 Correct 1243 ms 256000 KB Output is correct
5 Correct 971 ms 256000 KB Output is correct
6 Correct 1335 ms 254304 KB Output is correct
7 Correct 1387 ms 254200 KB Output is correct
8 Correct 1025 ms 254968 KB Output is correct
9 Correct 1471 ms 254080 KB Output is correct
10 Correct 1389 ms 253688 KB Output is correct
11 Correct 196 ms 251540 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 251384 KB Output is correct
2 Correct 187 ms 251512 KB Output is correct
3 Correct 189 ms 251416 KB Output is correct
4 Correct 184 ms 251452 KB Output is correct
5 Correct 198 ms 251428 KB Output is correct
6 Correct 189 ms 251484 KB Output is correct
7 Correct 182 ms 251512 KB Output is correct
8 Correct 187 ms 251356 KB Output is correct
9 Correct 195 ms 251640 KB Output is correct
10 Correct 192 ms 251548 KB Output is correct
11 Correct 185 ms 251384 KB Output is correct
12 Correct 1864 ms 256000 KB Output is correct
13 Correct 2718 ms 254044 KB Output is correct
14 Correct 827 ms 253688 KB Output is correct
15 Correct 3193 ms 254012 KB Output is correct
16 Correct 851 ms 253856 KB Output is correct
17 Correct 2015 ms 254512 KB Output is correct
18 Correct 3205 ms 254328 KB Output is correct
19 Correct 2724 ms 254376 KB Output is correct
20 Correct 2444 ms 253824 KB Output is correct
21 Correct 183 ms 251412 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 251384 KB Output is correct
2 Correct 183 ms 251376 KB Output is correct
3 Correct 184 ms 251540 KB Output is correct
4 Correct 190 ms 251404 KB Output is correct
5 Correct 187 ms 251384 KB Output is correct
6 Correct 186 ms 251432 KB Output is correct
7 Correct 183 ms 251384 KB Output is correct
8 Correct 181 ms 251384 KB Output is correct
9 Correct 190 ms 251384 KB Output is correct
10 Correct 184 ms 251536 KB Output is correct
11 Correct 209 ms 251384 KB Output is correct
12 Correct 1336 ms 256000 KB Output is correct
13 Correct 989 ms 256000 KB Output is correct
14 Correct 1413 ms 254448 KB Output is correct
15 Correct 1453 ms 254100 KB Output is correct
16 Correct 954 ms 254840 KB Output is correct
17 Correct 1481 ms 254044 KB Output is correct
18 Correct 1435 ms 253664 KB Output is correct
19 Correct 1916 ms 256000 KB Output is correct
20 Correct 2746 ms 253880 KB Output is correct
21 Correct 880 ms 253828 KB Output is correct
22 Correct 3273 ms 254072 KB Output is correct
23 Correct 881 ms 253912 KB Output is correct
24 Correct 1943 ms 254440 KB Output is correct
25 Correct 3014 ms 252636 KB Output is correct
26 Correct 2756 ms 252920 KB Output is correct
27 Correct 2551 ms 252276 KB Output is correct
28 Correct 1188 ms 252280 KB Output is correct
29 Correct 2975 ms 255200 KB Output is correct
30 Correct 7289 ms 252044 KB Output is correct
31 Correct 6583 ms 252188 KB Output is correct
32 Correct 851 ms 252024 KB Output is correct
33 Correct 1067 ms 252192 KB Output is correct
34 Correct 1560 ms 252352 KB Output is correct
35 Correct 2225 ms 252932 KB Output is correct
36 Correct 4165 ms 252752 KB Output is correct
37 Correct 3353 ms 252756 KB Output is correct
38 Correct 3436 ms 252408 KB Output is correct
39 Correct 2980 ms 254708 KB Output is correct
40 Correct 189 ms 251384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 251420 KB Output is correct
2 Correct 195 ms 251384 KB Output is correct
3 Correct 193 ms 251344 KB Output is correct
4 Correct 191 ms 251384 KB Output is correct
5 Correct 188 ms 251516 KB Output is correct
6 Correct 183 ms 251384 KB Output is correct
7 Correct 188 ms 251472 KB Output is correct
8 Correct 191 ms 251420 KB Output is correct
9 Correct 191 ms 251360 KB Output is correct
10 Correct 192 ms 251356 KB Output is correct
11 Correct 191 ms 251388 KB Output is correct
12 Correct 1317 ms 256000 KB Output is correct
13 Correct 1014 ms 256000 KB Output is correct
14 Correct 1425 ms 255416 KB Output is correct
15 Correct 1393 ms 255248 KB Output is correct
16 Correct 945 ms 255864 KB Output is correct
17 Correct 1415 ms 255116 KB Output is correct
18 Correct 1341 ms 255096 KB Output is correct
19 Correct 1887 ms 256000 KB Output is correct
20 Correct 2718 ms 254880 KB Output is correct
21 Correct 825 ms 254820 KB Output is correct
22 Correct 3160 ms 255028 KB Output is correct
23 Correct 894 ms 254972 KB Output is correct
24 Correct 2035 ms 255520 KB Output is correct
25 Correct 3111 ms 254780 KB Output is correct
26 Correct 2712 ms 254112 KB Output is correct
27 Correct 2830 ms 253616 KB Output is correct
28 Correct 1356 ms 253316 KB Output is correct
29 Correct 3062 ms 256000 KB Output is correct
30 Correct 7281 ms 253304 KB Output is correct
31 Correct 6669 ms 253948 KB Output is correct
32 Correct 862 ms 253348 KB Output is correct
33 Correct 1087 ms 253804 KB Output is correct
34 Correct 1596 ms 253816 KB Output is correct
35 Correct 2264 ms 254412 KB Output is correct
36 Correct 4223 ms 254088 KB Output is correct
37 Correct 3718 ms 254200 KB Output is correct
38 Correct 3410 ms 253608 KB Output is correct
39 Execution timed out 13025 ms 256000 KB Time limit exceeded
40 Halted 0 ms 0 KB -