oj.uz

Submission #43167

# Submission time Handle Problem Language Result Execution time Memory
43167 2018-03-09T17:09:00 Z yusufake Game (IOI13_game) C++
80 / 100
 10522 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;
 
inline ll gcd(ll u, ll v) {
    ll r;
    while (v != 0) { r = u % v; u = v; v = r; }
    return u;
}

inline 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));
}
inline 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){  // s[0] should contain ineffective element
	if(tl == tr){
		s[v] = r1 || r2 ? gcd(s[r1] , s[r2]) : tt;
		return;
	}
    int &l = L[v];
    int &r = R[v];
	if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
	else          { if(!l) l = ++id; up_y(l,tl,tm,L[r1],L[r2]); }
	s[v] = gcd(s[l] , s[r]);
}
void up_x(_){
    int &l = L[v];
    int &r = R[v];
	if(tl < tr){
		if(posx > tm) { if(!r) r = ++id; up_x(r,tm+1,tr); }
		else          { if(!l) l = ++id; up_x(l,tl,tm); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,Y[l],Y[r]);
}
 
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:34: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:34: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:39: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:39: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:49:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
            ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:49:42: note: in expansion of macro 'tm'
  if(posy > tm) { if(!r) r = ++id; up_y(r,tm+1,tr,R[r1],R[r2]); }
                                          ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:50:45: note: in expansion of macro 'tm'
  else          { if(!l) l = ++id; up_y(l,tl,tm,L[r1],L[r2]); }
                                             ^
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) r = ++id; up_x(r,tm+1,tr); }
             ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:57:43: note: in expansion of macro 'tm'
   if(posx > tm) { if(!r) r = ++id; up_x(r,tm+1,tr); }
                                           ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:58:46: note: in expansion of macro 'tm'
   else          { if(!l) l = ++id; up_x(l,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 5 ms 608 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 4 ms 960 KB Output is correct
7 Correct 2 ms 960 KB Output is correct
8 Correct 2 ms 960 KB Output is correct
9 Correct 4 ms 960 KB Output is correct
10 Correct 2 ms 960 KB Output is correct
11 Correct 3 ms 960 KB Output is correct
12 Correct 2 ms 960 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 960 KB Output is correct
2 Correct 2 ms 960 KB Output is correct
3 Correct 2 ms 960 KB Output is correct
4 Correct 1100 ms 32080 KB Output is correct
5 Correct 806 ms 36464 KB Output is correct
6 Correct 1370 ms 38112 KB Output is correct
7 Correct 1348 ms 42276 KB Output is correct
8 Correct 801 ms 42276 KB Output is correct
9 Correct 1376 ms 51388 KB Output is correct
10 Correct 1214 ms 55616 KB Output is correct
11 Correct 2 ms 55616 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 55616 KB Output is correct
2 Correct 4 ms 55616 KB Output is correct
3 Correct 4 ms 55616 KB Output is correct
4 Correct 2 ms 55616 KB Output is correct
5 Correct 2 ms 55616 KB Output is correct
6 Correct 4 ms 55616 KB Output is correct
7 Correct 2 ms 55616 KB Output is correct
8 Correct 2 ms 55616 KB Output is correct
9 Correct 3 ms 55616 KB Output is correct
10 Correct 2 ms 55616 KB Output is correct
11 Correct 3 ms 55616 KB Output is correct
12 Correct 1479 ms 55616 KB Output is correct
13 Correct 2462 ms 55616 KB Output is correct
14 Correct 574 ms 55616 KB Output is correct
15 Correct 2805 ms 57876 KB Output is correct
16 Correct 576 ms 67580 KB Output is correct
17 Correct 1653 ms 68820 KB Output is correct
18 Correct 2646 ms 78140 KB Output is correct
19 Correct 2291 ms 83704 KB Output is correct
20 Correct 2134 ms 88420 KB Output is correct
21 Correct 2 ms 88420 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 88420 KB Output is correct
2 Correct 4 ms 88420 KB Output is correct
3 Correct 4 ms 88420 KB Output is correct
4 Correct 2 ms 88420 KB Output is correct
5 Correct 2 ms 88420 KB Output is correct
6 Correct 3 ms 88420 KB Output is correct
7 Correct 1 ms 88420 KB Output is correct
8 Correct 2 ms 88420 KB Output is correct
9 Correct 3 ms 88420 KB Output is correct
10 Correct 3 ms 88420 KB Output is correct
11 Correct 3 ms 88420 KB Output is correct
12 Correct 1059 ms 105728 KB Output is correct
13 Correct 738 ms 109824 KB Output is correct
14 Correct 1186 ms 111552 KB Output is correct
15 Correct 1197 ms 115820 KB Output is correct
16 Correct 772 ms 115820 KB Output is correct
17 Correct 1234 ms 124884 KB Output is correct
18 Correct 1094 ms 129160 KB Output is correct
19 Correct 1456 ms 129160 KB Output is correct
20 Correct 2378 ms 129160 KB Output is correct
21 Correct 629 ms 129160 KB Output is correct
22 Correct 2664 ms 131272 KB Output is correct
23 Correct 612 ms 141164 KB Output is correct
24 Correct 1595 ms 142384 KB Output is correct
25 Correct 2541 ms 151676 KB Output is correct
26 Correct 2215 ms 157084 KB Output is correct
27 Correct 2008 ms 161960 KB Output is correct
28 Correct 1123 ms 256000 KB Output is correct
29 Correct 2844 ms 256000 KB Output is correct
30 Correct 7056 ms 256000 KB Output is correct
31 Correct 6404 ms 256000 KB Output is correct
32 Correct 700 ms 256000 KB Output is correct
33 Correct 995 ms 256000 KB Output is correct
34 Correct 1731 ms 256000 KB Output is correct
35 Correct 2090 ms 256000 KB Output is correct
36 Correct 3926 ms 256000 KB Output is correct
37 Correct 3207 ms 256000 KB Output is correct
38 Correct 3037 ms 256000 KB Output is correct
39 Correct 2649 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 2 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 1 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 1022 ms 256000 KB Output is correct
13 Correct 781 ms 256000 KB Output is correct
14 Correct 1254 ms 256000 KB Output is correct
15 Correct 1261 ms 256000 KB Output is correct
16 Correct 763 ms 256000 KB Output is correct
17 Correct 1311 ms 256000 KB Output is correct
18 Correct 1131 ms 256000 KB Output is correct
19 Correct 1474 ms 256000 KB Output is correct
20 Correct 2426 ms 256000 KB Output is correct
21 Correct 567 ms 256000 KB Output is correct
22 Correct 2698 ms 256000 KB Output is correct
23 Correct 577 ms 256000 KB Output is correct
24 Correct 1581 ms 256000 KB Output is correct
25 Correct 2530 ms 256000 KB Output is correct
26 Correct 2356 ms 256000 KB Output is correct
27 Correct 2146 ms 256000 KB Output is correct
28 Correct 1165 ms 256000 KB Output is correct
29 Correct 2703 ms 256000 KB Output is correct
30 Correct 7073 ms 256000 KB Output is correct
31 Correct 6644 ms 256000 KB Output is correct
32 Correct 701 ms 256000 KB Output is correct
33 Correct 1002 ms 256000 KB Output is correct
34 Correct 1784 ms 256000 KB Output is correct
35 Correct 2088 ms 256000 KB Output is correct
36 Correct 3728 ms 256000 KB Output is correct
37 Correct 3316 ms 256000 KB Output is correct
38 Correct 3232 ms 256000 KB Output is correct
39 Execution timed out 10522 ms 256000 KB Time limit exceeded (wall clock)
40 Halted 0 ms 0 KB -