oj.uz

Submission #42770

# Submission time Handle Problem Language Result Execution time Memory
42770 2018-03-03T22:51:17 Z yusufake Game (IOI13_game) C++
80 / 100
 12002 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 * 500;
 
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 608 KB Output is correct
3 Correct 4 ms 680 KB Output is correct
4 Correct 1 ms 680 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 3 ms 680 KB Output is correct
7 Correct 1 ms 680 KB Output is correct
8 Correct 1 ms 680 KB Output is correct
9 Correct 4 ms 788 KB Output is correct
10 Correct 2 ms 788 KB Output is correct
11 Correct 2 ms 788 KB Output is correct
12 Correct 1 ms 788 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 788 KB Output is correct
2 Correct 1 ms 788 KB Output is correct
3 Correct 1 ms 788 KB Output is correct
4 Correct 1146 ms 30448 KB Output is correct
5 Correct 871 ms 34624 KB Output is correct
6 Correct 1247 ms 36160 KB Output is correct
7 Correct 1238 ms 40740 KB Output is correct
8 Correct 822 ms 40740 KB Output is correct
9 Correct 1274 ms 49580 KB Output is correct
10 Correct 1199 ms 54040 KB Output is correct
11 Correct 2 ms 54040 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 54040 KB Output is correct
2 Correct 4 ms 54040 KB Output is correct
3 Correct 4 ms 54040 KB Output is correct
4 Correct 1 ms 54040 KB Output is correct
5 Correct 1 ms 54040 KB Output is correct
6 Correct 4 ms 54040 KB Output is correct
7 Correct 2 ms 54040 KB Output is correct
8 Correct 1 ms 54040 KB Output is correct
9 Correct 3 ms 54040 KB Output is correct
10 Correct 3 ms 54040 KB Output is correct
11 Correct 2 ms 54040 KB Output is correct
12 Correct 1815 ms 54040 KB Output is correct
13 Correct 2744 ms 54040 KB Output is correct
14 Correct 661 ms 54040 KB Output is correct
15 Correct 3269 ms 54040 KB Output is correct
16 Correct 698 ms 54040 KB Output is correct
17 Correct 1711 ms 54040 KB Output is correct
18 Correct 2708 ms 58796 KB Output is correct
19 Correct 2379 ms 64228 KB Output is correct
20 Correct 2259 ms 68832 KB Output is correct
21 Correct 2 ms 68832 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 68832 KB Output is correct
2 Correct 4 ms 68832 KB Output is correct
3 Correct 4 ms 68832 KB Output is correct
4 Correct 2 ms 68832 KB Output is correct
5 Correct 2 ms 68832 KB Output is correct
6 Correct 3 ms 68832 KB Output is correct
7 Correct 2 ms 68832 KB Output is correct
8 Correct 2 ms 68832 KB Output is correct
9 Correct 3 ms 68832 KB Output is correct
10 Correct 2 ms 68832 KB Output is correct
11 Correct 2 ms 68832 KB Output is correct
12 Correct 1237 ms 84696 KB Output is correct
13 Correct 883 ms 88772 KB Output is correct
14 Correct 1299 ms 90404 KB Output is correct
15 Correct 1307 ms 94752 KB Output is correct
16 Correct 820 ms 94752 KB Output is correct
17 Correct 1296 ms 103892 KB Output is correct
18 Correct 1201 ms 108160 KB Output is correct
19 Correct 1725 ms 108160 KB Output is correct
20 Correct 2770 ms 108160 KB Output is correct
21 Correct 686 ms 108160 KB Output is correct
22 Correct 3251 ms 110048 KB Output is correct
23 Correct 748 ms 120080 KB Output is correct
24 Correct 1707 ms 121096 KB Output is correct
25 Correct 2782 ms 130488 KB Output is correct
26 Correct 2446 ms 135952 KB Output is correct
27 Correct 2296 ms 140676 KB Output is correct
28 Correct 1203 ms 256000 KB Output is correct
29 Correct 2866 ms 256000 KB Output is correct
30 Correct 8239 ms 256000 KB Output is correct
31 Correct 7566 ms 256000 KB Output is correct
32 Correct 761 ms 256000 KB Output is correct
33 Correct 1008 ms 256000 KB Output is correct
34 Correct 1750 ms 256000 KB Output is correct
35 Correct 2045 ms 256000 KB Output is correct
36 Correct 3932 ms 256000 KB Output is correct
37 Correct 3171 ms 256000 KB Output is correct
38 Correct 3094 ms 256000 KB Output is correct
39 Correct 2678 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 2 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 1 ms 256000 KB Output is correct
5 Correct 1 ms 256000 KB Output is correct
6 Correct 4 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 1160 ms 256000 KB Output is correct
13 Correct 912 ms 256000 KB Output is correct
14 Correct 1314 ms 256000 KB Output is correct
15 Correct 1405 ms 256000 KB Output is correct
16 Correct 812 ms 256000 KB Output is correct
17 Correct 1339 ms 256000 KB Output is correct
18 Correct 1177 ms 256000 KB Output is correct
19 Correct 1747 ms 256000 KB Output is correct
20 Correct 2810 ms 256000 KB Output is correct
21 Correct 686 ms 256000 KB Output is correct
22 Correct 3204 ms 256000 KB Output is correct
23 Correct 701 ms 256000 KB Output is correct
24 Correct 1658 ms 256000 KB Output is correct
25 Correct 2596 ms 256000 KB Output is correct
26 Correct 2316 ms 256000 KB Output is correct
27 Correct 2168 ms 256000 KB Output is correct
28 Correct 1164 ms 256000 KB Output is correct
29 Correct 2902 ms 256000 KB Output is correct
30 Correct 8237 ms 256000 KB Output is correct
31 Correct 7533 ms 256000 KB Output is correct
32 Correct 793 ms 256000 KB Output is correct
33 Correct 1010 ms 256000 KB Output is correct
34 Correct 1723 ms 256000 KB Output is correct
35 Correct 2075 ms 256000 KB Output is correct
36 Correct 3821 ms 256000 KB Output is correct
37 Correct 3342 ms 256000 KB Output is correct
38 Correct 3198 ms 256000 KB Output is correct
39 Runtime error 12002 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -