oj.uz

Submission #42771

# Submission time Handle Problem Language Result Execution time Memory
42771 2018-03-03T22:58:30 Z yusufake Game (IOI13_game) C++
80 / 100
 12540 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 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(int v, int tl, int tr) { 
	if(ly > tr || ry < tl || !v) return 0;
	if (ly <= tl && tr <= ry) return s[v];
	return gcd(qry_y(L[v],tl,tm) , qry_y(R[v],tm+1,tr));
}
ll qry_x(int v, int tl, int tr) { 
	if(lx > tr || rx < tl) return 0;
	if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod);
	return gcd(qry_x(L[v],tl,tm) , qry_x(R[v],tm+1,tr));
}
 
void up_y(int v, int tl, int tr, int r1, int r2, bool h){ 
	if(tl == tr){
		s[v] = h ? tt : gcd(s[r1] , s[r2]);
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(R[v],tm+1,tr,R[r1],R[r2],h); }
	else          { if(!L[v]) L[v] = ++id; up_y(L[v],tl,tm,L[r1],L[r2],h); }
	s[v] = gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(int v, int tl, int tr){
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(R[v],tm+1,tr); }
		else          { if(!L[v]) L[v] = ++id; up_x(L[v],tl,tm); }
	}
	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:36:27: note: in expansion of macro 'tm'
  return gcd(qry_y(L[v],tl,tm) , qry_y(R[v],tm+1,tr));
                           ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:36:44: note: in expansion of macro 'tm'
  return gcd(qry_y(L[v],tl,tm) , qry_y(R[v],tm+1,tr));
                                            ^
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:41:27: note: in expansion of macro 'tm'
  return gcd(qry_x(L[v],tl,tm) , qry_x(R[v],tm+1,tr));
                           ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:41:44: note: in expansion of macro 'tm'
  return gcd(qry_x(L[v],tl,tm) , qry_x(R[v],tm+1,tr));
                                            ^
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:49:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(R[v],tm+1,tr,R[r1],R[r2],h); }
            ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:49:51: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(R[v],tm+1,tr,R[r1],R[r2],h); }
                                                   ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:50:54: note: in expansion of macro 'tm'
  else          { if(!L[v]) L[v] = ++id; up_y(L[v],tl,tm,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:55:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(R[v],tm+1,tr); }
             ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:55:52: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(R[v],tm+1,tr); }
                                                    ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:56:55: note: in expansion of macro 'tm'
   else          { if(!L[v]) L[v] = ++id; up_x(L[v],tl,tm); }
                                                       ^

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 736 KB Output is correct
3 Correct 4 ms 736 KB Output is correct
4 Correct 1 ms 736 KB Output is correct
5 Correct 1 ms 736 KB Output is correct
6 Correct 3 ms 752 KB Output is correct
7 Correct 1 ms 752 KB Output is correct
8 Correct 1 ms 752 KB Output is correct
9 Correct 3 ms 752 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 2 ms 752 KB Output is correct
12 Correct 1 ms 752 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 752 KB Output is correct
2 Correct 1 ms 752 KB Output is correct
3 Correct 1 ms 752 KB Output is correct
4 Correct 1151 ms 30432 KB Output is correct
5 Correct 849 ms 34532 KB Output is correct
6 Correct 1233 ms 36192 KB Output is correct
7 Correct 1281 ms 40640 KB Output is correct
8 Correct 832 ms 40640 KB Output is correct
9 Correct 1311 ms 49624 KB Output is correct
10 Correct 1219 ms 53940 KB Output is correct
11 Correct 1 ms 53940 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 53940 KB Output is correct
2 Correct 4 ms 53940 KB Output is correct
3 Correct 4 ms 53940 KB Output is correct
4 Correct 1 ms 53940 KB Output is correct
5 Correct 1 ms 53940 KB Output is correct
6 Correct 4 ms 53940 KB Output is correct
7 Correct 2 ms 53940 KB Output is correct
8 Correct 1 ms 53940 KB Output is correct
9 Correct 3 ms 53940 KB Output is correct
10 Correct 2 ms 53940 KB Output is correct
11 Correct 3 ms 53940 KB Output is correct
12 Correct 1831 ms 53940 KB Output is correct
13 Correct 2736 ms 53940 KB Output is correct
14 Correct 680 ms 53940 KB Output is correct
15 Correct 3190 ms 53940 KB Output is correct
16 Correct 713 ms 53940 KB Output is correct
17 Correct 1656 ms 53940 KB Output is correct
18 Correct 2781 ms 58572 KB Output is correct
19 Correct 2377 ms 64196 KB Output is correct
20 Correct 2197 ms 68864 KB Output is correct
21 Correct 2 ms 68864 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 68864 KB Output is correct
2 Correct 4 ms 68864 KB Output is correct
3 Correct 4 ms 68864 KB Output is correct
4 Correct 2 ms 68864 KB Output is correct
5 Correct 2 ms 68864 KB Output is correct
6 Correct 4 ms 68864 KB Output is correct
7 Correct 2 ms 68864 KB Output is correct
8 Correct 3 ms 68864 KB Output is correct
9 Correct 3 ms 68864 KB Output is correct
10 Correct 2 ms 68864 KB Output is correct
11 Correct 2 ms 68864 KB Output is correct
12 Correct 1186 ms 84644 KB Output is correct
13 Correct 913 ms 88840 KB Output is correct
14 Correct 1319 ms 90292 KB Output is correct
15 Correct 1325 ms 94960 KB Output is correct
16 Correct 810 ms 94960 KB Output is correct
17 Correct 1283 ms 103880 KB Output is correct
18 Correct 1154 ms 108068 KB Output is correct
19 Correct 1746 ms 108068 KB Output is correct
20 Correct 2702 ms 108068 KB Output is correct
21 Correct 681 ms 108068 KB Output is correct
22 Correct 3124 ms 110264 KB Output is correct
23 Correct 690 ms 120080 KB Output is correct
24 Correct 1621 ms 121080 KB Output is correct
25 Correct 2599 ms 130440 KB Output is correct
26 Correct 2274 ms 135988 KB Output is correct
27 Correct 2036 ms 140728 KB Output is correct
28 Correct 1151 ms 256000 KB Output is correct
29 Correct 2894 ms 256000 KB Output is correct
30 Correct 8082 ms 256000 KB Output is correct
31 Correct 7484 ms 256000 KB Output is correct
32 Correct 765 ms 256000 KB Output is correct
33 Correct 997 ms 256000 KB Output is correct
34 Correct 1758 ms 256000 KB Output is correct
35 Correct 2050 ms 256000 KB Output is correct
36 Correct 3751 ms 256000 KB Output is correct
37 Correct 3352 ms 256000 KB Output is correct
38 Correct 3302 ms 256000 KB Output is correct
39 Correct 2602 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 3 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 1 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 1141 ms 256000 KB Output is correct
13 Correct 851 ms 256000 KB Output is correct
14 Correct 1217 ms 256000 KB Output is correct
15 Correct 1280 ms 256000 KB Output is correct
16 Correct 789 ms 256000 KB Output is correct
17 Correct 1262 ms 256000 KB Output is correct
18 Correct 1132 ms 256000 KB Output is correct
19 Correct 1712 ms 256000 KB Output is correct
20 Correct 2797 ms 256000 KB Output is correct
21 Correct 717 ms 256000 KB Output is correct
22 Correct 3129 ms 256000 KB Output is correct
23 Correct 674 ms 256000 KB Output is correct
24 Correct 1685 ms 256000 KB Output is correct
25 Correct 2693 ms 256000 KB Output is correct
26 Correct 2432 ms 256000 KB Output is correct
27 Correct 2230 ms 256000 KB Output is correct
28 Correct 1183 ms 256000 KB Output is correct
29 Correct 2924 ms 256000 KB Output is correct
30 Correct 8089 ms 256000 KB Output is correct
31 Correct 7434 ms 256000 KB Output is correct
32 Correct 766 ms 256000 KB Output is correct
33 Correct 1087 ms 256000 KB Output is correct
34 Correct 1748 ms 256000 KB Output is correct
35 Correct 2097 ms 256000 KB Output is correct
36 Correct 3945 ms 256000 KB Output is correct
37 Correct 3147 ms 256000 KB Output is correct
38 Correct 3069 ms 256000 KB Output is correct
39 Execution timed out 12540 ms 256000 KB Time limit exceeded (wall clock)
40 Halted 0 ms 0 KB -