oj.uz

Submission #122149

# Submission time Handle Problem Language Result Execution time Memory
122149 2019-06-27T17:32:15 Z yusufake Game (IOI13_game) C++
80 / 100
 13000 ms 230560 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 - 1;
const int N   = 22000 * 23 * 23;
 
int Y[N],L[N],R[N],id = 1;
ll s[N],t;
int posx,posy,lx,rx,ly,ry;
 
// 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(_) { 
	if(ly > tr || ry < tl || !v) return 0;
	if (ly <= tl && tr <= ry) return s[v];
	return gcd(qry_y(sol) , qry_y(sag));
}
ll qry_x(_) { 
	if(lx > tr || rx < tl) return 0;
	if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod);
	return gcd(qry_x(sol) , qry_x(sag));
}
 
void up_y(_, int r1, int r2){  
    if(id == N-2) while(1);
    if(tl == tr){
		s[v] = r1 || r2 ? gcd(s[r1] , s[r2]) : t;
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2]); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,L[r1],L[r2]); }
	s[v] = gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_){
    if(id == N-2) while(1);
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag); }
		else          { if(!L[v]) L[v] = ++id; up_x(sol); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,Y[ L[v] ],Y[ R[v] ]);
}
 
 
void update(int px, int py, ll tt){
    posx = px;
    posy = py;
    t = tt;
	up_x(1,0,mod);
}	
 
ll calculate(int aalx, int aaly, int aarx, int aary){
    lx = aalx; rx = aarx;
    ly = aaly; ry = aary;
	return qry_x(1,0,mod);
}	
 
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)':
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) , qry_y(sag));
                   ^~~
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:32: note: in expansion of macro 'sag'
  return gcd(qry_y(sol) , qry_y(sag));
                                ^~~
game.cpp: In function 'll qry_x(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) , qry_x(sag));
                   ^~~
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:32: note: in expansion of macro 'sag'
  return gcd(qry_x(sol) , qry_x(sag));
                                ^~~
game.cpp: In function 'void up_y(int, int, int, int, int)':
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,R[r1],R[r2]); }
            ^~
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,R[r1],R[r2]); }
                                              ^~~
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,L[r1],L[r2]); }
                                              ^~~
game.cpp: In function 'void up_x(int, int, int)':
game.cpp:60:19: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     if(id == N-2) 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); }
             ^~
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); }
                                               ^~~
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); }
                                               ^~~

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 640 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 640 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 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 1116 ms 29412 KB Output is correct
5 Correct 831 ms 29720 KB Output is correct
6 Correct 1266 ms 26860 KB Output is correct
7 Correct 1345 ms 26548 KB Output is correct
8 Correct 788 ms 17716 KB Output is correct
9 Correct 1351 ms 26612 KB Output is correct
10 Correct 1202 ms 26180 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 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 640 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 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1699 ms 14744 KB Output is correct
13 Correct 2380 ms 8120 KB Output is correct
14 Correct 570 ms 3212 KB Output is correct
15 Correct 2760 ms 11100 KB Output is correct
16 Correct 631 ms 16500 KB Output is correct
17 Correct 1727 ms 13052 KB Output is correct
18 Correct 2812 ms 17156 KB Output is correct
19 Correct 2514 ms 17208 KB Output is correct
20 Correct 2309 ms 16992 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 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 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 356 KB Output is correct
12 Correct 1089 ms 29468 KB Output is correct
13 Correct 842 ms 29736 KB Output is correct
14 Correct 1274 ms 26672 KB Output is correct
15 Correct 1226 ms 26380 KB Output is correct
16 Correct 770 ms 17656 KB Output is correct
17 Correct 1337 ms 26660 KB Output is correct
18 Correct 1193 ms 26316 KB Output is correct
19 Correct 1588 ms 14740 KB Output is correct
20 Correct 2504 ms 8012 KB Output is correct
21 Correct 570 ms 3268 KB Output is correct
22 Correct 2708 ms 11000 KB Output is correct
23 Correct 664 ms 16664 KB Output is correct
24 Correct 1717 ms 12984 KB Output is correct
25 Correct 2953 ms 16988 KB Output is correct
26 Correct 2380 ms 17164 KB Output is correct
27 Correct 2413 ms 16688 KB Output is correct
28 Correct 1162 ms 160496 KB Output is correct
29 Correct 2615 ms 179744 KB Output is correct
30 Correct 6610 ms 122544 KB Output is correct
31 Correct 6001 ms 94068 KB Output is correct
32 Correct 618 ms 5092 KB Output is correct
33 Correct 822 ms 6520 KB Output is correct
34 Correct 561 ms 175608 KB Output is correct
35 Correct 2146 ms 91920 KB Output is correct
36 Correct 4304 ms 176984 KB Output is correct
37 Correct 3230 ms 176568 KB Output is correct
38 Correct 3113 ms 176160 KB Output is correct
39 Correct 2804 ms 136624 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 640 KB Output is correct
3 Correct 4 ms 640 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 556 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1103 ms 29724 KB Output is correct
13 Correct 881 ms 29860 KB Output is correct
14 Correct 1411 ms 27000 KB Output is correct
15 Correct 1389 ms 26656 KB Output is correct
16 Correct 741 ms 17824 KB Output is correct
17 Correct 1388 ms 26776 KB Output is correct
18 Correct 1195 ms 26400 KB Output is correct
19 Correct 1614 ms 14944 KB Output is correct
20 Correct 2480 ms 8536 KB Output is correct
21 Correct 556 ms 3448 KB Output is correct
22 Correct 2637 ms 11296 KB Output is correct
23 Correct 630 ms 16972 KB Output is correct
24 Correct 1728 ms 13276 KB Output is correct
25 Correct 3015 ms 17172 KB Output is correct
26 Correct 2591 ms 17352 KB Output is correct
27 Correct 2353 ms 16704 KB Output is correct
28 Correct 1112 ms 160840 KB Output is correct
29 Correct 2762 ms 179704 KB Output is correct
30 Correct 6846 ms 123312 KB Output is correct
31 Correct 6142 ms 94728 KB Output is correct
32 Correct 624 ms 5088 KB Output is correct
33 Correct 803 ms 6752 KB Output is correct
34 Correct 554 ms 175784 KB Output is correct
35 Correct 1996 ms 91816 KB Output is correct
36 Correct 4159 ms 177168 KB Output is correct
37 Correct 3173 ms 177484 KB Output is correct
38 Correct 3068 ms 176952 KB Output is correct
39 Execution timed out 13094 ms 230560 KB Time limit exceeded
40 Halted 0 ms 0 KB -