oj.uz

Submission #121656

# Submission time Handle Problem Language Result Execution time Memory
121656 2019-06-26T22:38:34 Z yusufake Game (IOI13_game) C++
80 / 100
 13000 ms 228564 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 * 23 * 23;

int Y[N],L[N],R[N],id;
ll s[N];
 
// 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(_, int ly, int ry) { 
	if(ly > tr || ry < tl || !v) return 0;
	if (ly <= tl && tr <= ry) return s[v];
	return gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
}
ll qry_x(_, int lx, int rx, int ly, int ry) { 
	if(lx > tr || rx < tl) return 0;
	if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod, ly, ry);
	return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
}
 
void up_y(_, int posy, int r1, int r2, ll t){  
    if(id == N - 5) while(1);
    if(tl == tr){
		s[v] = t == -1 ? gcd(s[r1] , s[r2]) : t;
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,posy,L[r1],L[r2],t); }
	s[v] = gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_, int posx, int posy, ll t){
    if(id == N - 5) while(1);
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
		else          { if(!L[v]) L[v] = ++id; up_x(sol,posx,posy,t); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,posy,Y[ L[v] ],Y[ R[v] ],(tl==tr?t:-1));
}
 
 
void update(int posx, int posy, ll t){
	up_x(1,0,mod,posx,posy,t);
}	

ll calculate(int lx, int ly, int rx, int ry){
	return qry_x(1,0,mod,lx,rx,ly,ry);
}	
 
void init(int a, int b) {
//    memset(s , 0 , sizeof s);
//    memset(Y , 0 , sizeof Y);
//    memset(L , 0 , sizeof L);
//    memset(R , 0 , sizeof R);
    id = 1;
}

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, 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:40:19: note: in expansion of macro 'sol'
  return gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
                   ^~~
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:40:38: note: in expansion of macro 'sag'
  return gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
                                      ^~~
game.cpp: In function 'll qry_x(int, int, int, int, 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:45:19: note: in expansion of macro 'sol'
  return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
                   ^~~
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:45:44: note: in expansion of macro 'sag'
  return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
                                            ^~~
game.cpp: In function 'void up_y(int, int, int, int, int, int, ll)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:54:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
            ^~
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:54:46: note: in expansion of macro 'sag'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
                                              ^~~
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:55:46: note: in expansion of macro 'sol'
  else          { if(!L[v]) L[v] = ++id; up_y(sol,posy,L[r1],L[r2],t); }
                                              ^~~
game.cpp: In function 'void up_x(int, int, int, int, int, ll)':
game.cpp:59:21: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     if(id == N - 5) while(1);
                     ^~~~~
game.cpp:60: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:61:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
             ^~
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:61:47: note: in expansion of macro 'sag'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
                                               ^~~
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:62:47: note: in expansion of macro 'sol'
   else          { if(!L[v]) L[v] = ++id; up_x(sol,posx,posy,t); }
                                               ^~~

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 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 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 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 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 1096 ms 27464 KB Output is correct
5 Correct 835 ms 27748 KB Output is correct
6 Correct 1229 ms 24608 KB Output is correct
7 Correct 1292 ms 24440 KB Output is correct
8 Correct 793 ms 15596 KB Output is correct
9 Correct 1277 ms 24424 KB Output is correct
10 Correct 1135 ms 24132 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 512 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 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1660 ms 12740 KB Output is correct
13 Correct 2494 ms 6212 KB Output is correct
14 Correct 628 ms 1144 KB Output is correct
15 Correct 2906 ms 9004 KB Output is correct
16 Correct 694 ms 14544 KB Output is correct
17 Correct 1812 ms 11020 KB Output is correct
18 Correct 3092 ms 15040 KB Output is correct
19 Correct 2563 ms 15192 KB Output is correct
20 Correct 2352 ms 14448 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 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 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 4 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1128 ms 27404 KB Output is correct
13 Correct 862 ms 27512 KB Output is correct
14 Correct 1455 ms 24592 KB Output is correct
15 Correct 1348 ms 24404 KB Output is correct
16 Correct 833 ms 15508 KB Output is correct
17 Correct 1400 ms 24704 KB Output is correct
18 Correct 1188 ms 24284 KB Output is correct
19 Correct 1684 ms 12788 KB Output is correct
20 Correct 2531 ms 6148 KB Output is correct
21 Correct 623 ms 1096 KB Output is correct
22 Correct 2952 ms 9100 KB Output is correct
23 Correct 671 ms 14556 KB Output is correct
24 Correct 1754 ms 10856 KB Output is correct
25 Correct 3012 ms 14928 KB Output is correct
26 Correct 2592 ms 15064 KB Output is correct
27 Correct 2408 ms 14624 KB Output is correct
28 Correct 1146 ms 157564 KB Output is correct
29 Correct 2965 ms 176036 KB Output is correct
30 Correct 7448 ms 119636 KB Output is correct
31 Correct 7177 ms 91792 KB Output is correct
32 Correct 692 ms 1320 KB Output is correct
33 Correct 920 ms 2768 KB Output is correct
34 Correct 1566 ms 173016 KB Output is correct
35 Correct 2400 ms 88156 KB Output is correct
36 Correct 4293 ms 173488 KB Output is correct
37 Correct 3387 ms 173532 KB Output is correct
38 Correct 3370 ms 172856 KB Output is correct
39 Correct 2907 ms 133180 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 3 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 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 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 1150 ms 27500 KB Output is correct
13 Correct 848 ms 27676 KB Output is correct
14 Correct 1212 ms 24708 KB Output is correct
15 Correct 1259 ms 24388 KB Output is correct
16 Correct 805 ms 15736 KB Output is correct
17 Correct 1321 ms 24372 KB Output is correct
18 Correct 1184 ms 24024 KB Output is correct
19 Correct 1656 ms 12612 KB Output is correct
20 Correct 2552 ms 6108 KB Output is correct
21 Correct 647 ms 1144 KB Output is correct
22 Correct 2903 ms 8876 KB Output is correct
23 Correct 680 ms 14716 KB Output is correct
24 Correct 1721 ms 10956 KB Output is correct
25 Correct 2923 ms 15000 KB Output is correct
26 Correct 2542 ms 15016 KB Output is correct
27 Correct 2261 ms 14424 KB Output is correct
28 Correct 1142 ms 157688 KB Output is correct
29 Correct 2856 ms 175968 KB Output is correct
30 Correct 7339 ms 119928 KB Output is correct
31 Correct 6655 ms 91672 KB Output is correct
32 Correct 692 ms 1400 KB Output is correct
33 Correct 921 ms 2936 KB Output is correct
34 Correct 1551 ms 173148 KB Output is correct
35 Correct 2146 ms 88056 KB Output is correct
36 Correct 4347 ms 173480 KB Output is correct
37 Correct 3469 ms 173492 KB Output is correct
38 Correct 3529 ms 172888 KB Output is correct
39 Execution timed out 13103 ms 228564 KB Time limit exceeded
40 Halted 0 ms 0 KB -