oj.uz

Submission #43146

# Submission time Handle Problem Language Result Execution time Memory
43146 2018-03-09T14:02:28 Z yusufake Game (IOI13_game) C++
80 / 100
 10496 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 * 525;
 
int Y[N],L[N],R[N],posx,posy,lx,ly,rx,ry,id=1;
ll s[N],tt;
 
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, bool h){  // s[0] should contain ineffective element
	if(tl == tr){
		s[v] = h ? tt : gcd(s[r1] , s[r2]);
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,L[r1],L[r2],h); }
	s[v] = gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_){
	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] ],(tl==tr));
}
 
void update(int x, int y, ll t){
	posx = x;
	posy = y;
	tt = t;
	up_x(1,0,mod);
}	
ll calculate(int a, int b, int a2, int b2){
	lx = a; ly = b;
	rx = a2; ry = b2;
	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:38: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:38: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:43: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:43: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, bool)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:51:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
            ^
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:51:46: note: in expansion of macro 'sag'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
                                              ^
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:52:46: note: in expansion of macro 'sol'
  else          { if(!L[v]) L[v] = ++id; up_y(sol,L[r1],L[r2],h); }
                                              ^
game.cpp: In function 'void up_x(int, int, int)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:57: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:57: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:58: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 376 KB Output is correct
2 Correct 4 ms 620 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 5 ms 788 KB Output is correct
7 Correct 2 ms 788 KB Output is correct
8 Correct 2 ms 788 KB Output is correct
9 Correct 3 ms 936 KB Output is correct
10 Correct 3 ms 936 KB Output is correct
11 Correct 3 ms 936 KB Output is correct
12 Correct 2 ms 936 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 936 KB Output is correct
2 Correct 2 ms 936 KB Output is correct
3 Correct 2 ms 936 KB Output is correct
4 Correct 1220 ms 32260 KB Output is correct
5 Correct 956 ms 36472 KB Output is correct
6 Correct 1346 ms 38032 KB Output is correct
7 Correct 1377 ms 42296 KB Output is correct
8 Correct 844 ms 42296 KB Output is correct
9 Correct 1389 ms 51536 KB Output is correct
10 Correct 1253 ms 55688 KB Output is correct
11 Correct 2 ms 55688 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 55688 KB Output is correct
2 Correct 4 ms 55688 KB Output is correct
3 Correct 4 ms 55688 KB Output is correct
4 Correct 1 ms 55688 KB Output is correct
5 Correct 1 ms 55688 KB Output is correct
6 Correct 3 ms 55688 KB Output is correct
7 Correct 2 ms 55688 KB Output is correct
8 Correct 2 ms 55688 KB Output is correct
9 Correct 3 ms 55688 KB Output is correct
10 Correct 2 ms 55688 KB Output is correct
11 Correct 3 ms 55688 KB Output is correct
12 Correct 1811 ms 55688 KB Output is correct
13 Correct 2800 ms 55688 KB Output is correct
14 Correct 721 ms 55688 KB Output is correct
15 Correct 3269 ms 57760 KB Output is correct
16 Correct 723 ms 67740 KB Output is correct
17 Correct 1757 ms 68948 KB Output is correct
18 Correct 2801 ms 78288 KB Output is correct
19 Correct 2503 ms 83680 KB Output is correct
20 Correct 2200 ms 88496 KB Output is correct
21 Correct 2 ms 88496 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 88496 KB Output is correct
2 Correct 4 ms 88496 KB Output is correct
3 Correct 4 ms 88496 KB Output is correct
4 Correct 1 ms 88496 KB Output is correct
5 Correct 2 ms 88496 KB Output is correct
6 Correct 3 ms 88496 KB Output is correct
7 Correct 2 ms 88496 KB Output is correct
8 Correct 2 ms 88496 KB Output is correct
9 Correct 4 ms 88496 KB Output is correct
10 Correct 3 ms 88496 KB Output is correct
11 Correct 2 ms 88496 KB Output is correct
12 Correct 1174 ms 105604 KB Output is correct
13 Correct 953 ms 109976 KB Output is correct
14 Correct 1332 ms 111768 KB Output is correct
15 Correct 1414 ms 115936 KB Output is correct
16 Correct 887 ms 115936 KB Output is correct
17 Correct 1350 ms 124996 KB Output is correct
18 Correct 1293 ms 129328 KB Output is correct
19 Correct 1778 ms 129328 KB Output is correct
20 Correct 2785 ms 129328 KB Output is correct
21 Correct 705 ms 129328 KB Output is correct
22 Correct 3296 ms 131412 KB Output is correct
23 Correct 716 ms 141032 KB Output is correct
24 Correct 1796 ms 142348 KB Output is correct
25 Correct 2986 ms 151620 KB Output is correct
26 Correct 2427 ms 157172 KB Output is correct
27 Correct 2283 ms 161936 KB Output is correct
28 Correct 1190 ms 256000 KB Output is correct
29 Correct 2976 ms 256000 KB Output is correct
30 Correct 8232 ms 256000 KB Output is correct
31 Correct 7938 ms 256000 KB Output is correct
32 Correct 823 ms 256000 KB Output is correct
33 Correct 1047 ms 256000 KB Output is correct
34 Correct 1797 ms 256000 KB Output is correct
35 Correct 2358 ms 256000 KB Output is correct
36 Correct 4673 ms 256000 KB Output is correct
37 Correct 3686 ms 256000 KB Output is correct
38 Correct 3423 ms 256000 KB Output is correct
39 Correct 2898 ms 256000 KB Output is correct
40 Correct 2 ms 256000 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256000 KB Output is correct
2 Correct 4 ms 256000 KB Output is correct
3 Correct 4 ms 256000 KB Output is correct
4 Correct 2 ms 256000 KB Output is correct
5 Correct 2 ms 256000 KB Output is correct
6 Correct 3 ms 256000 KB Output is correct
7 Correct 2 ms 256000 KB Output is correct
8 Correct 2 ms 256000 KB Output is correct
9 Correct 3 ms 256000 KB Output is correct
10 Correct 2 ms 256000 KB Output is correct
11 Correct 2 ms 256000 KB Output is correct
12 Correct 1190 ms 256000 KB Output is correct
13 Correct 945 ms 256000 KB Output is correct
14 Correct 1374 ms 256000 KB Output is correct
15 Correct 1349 ms 256000 KB Output is correct
16 Correct 898 ms 256000 KB Output is correct
17 Correct 1342 ms 256000 KB Output is correct
18 Correct 1252 ms 256000 KB Output is correct
19 Correct 1801 ms 256000 KB Output is correct
20 Correct 2756 ms 256000 KB Output is correct
21 Correct 693 ms 256000 KB Output is correct
22 Correct 3366 ms 256000 KB Output is correct
23 Correct 706 ms 256000 KB Output is correct
24 Correct 1798 ms 256000 KB Output is correct
25 Correct 3072 ms 256000 KB Output is correct
26 Correct 2592 ms 256000 KB Output is correct
27 Correct 2318 ms 256000 KB Output is correct
28 Correct 1241 ms 256000 KB Output is correct
29 Correct 3056 ms 256000 KB Output is correct
30 Correct 8319 ms 256000 KB Output is correct
31 Correct 8113 ms 256000 KB Output is correct
32 Correct 805 ms 256000 KB Output is correct
33 Correct 1027 ms 256000 KB Output is correct
34 Correct 1784 ms 256000 KB Output is correct
35 Correct 2407 ms 256000 KB Output is correct
36 Correct 4394 ms 256000 KB Output is correct
37 Correct 3577 ms 256000 KB Output is correct
38 Correct 3480 ms 256000 KB Output is correct
39 Execution timed out 10496 ms 256000 KB Time limit exceeded (wall clock)
40 Halted 0 ms 0 KB -