oj.uz

Submission #121966

# Submission time Handle Problem Language Result Execution time Memory
121966 2019-06-27T09:58:28 Z yusufake Game (IOI13_game) C++
80 / 100
 7487 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 * 27 * 27;

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 93 ms 126072 KB Output is correct
2 Correct 94 ms 126072 KB Output is correct
3 Correct 95 ms 126072 KB Output is correct
4 Correct 92 ms 125816 KB Output is correct
5 Correct 93 ms 125924 KB Output is correct
6 Correct 94 ms 125944 KB Output is correct
7 Correct 93 ms 125944 KB Output is correct
8 Correct 93 ms 125944 KB Output is correct
9 Correct 94 ms 125984 KB Output is correct
10 Correct 96 ms 126200 KB Output is correct
11 Correct 93 ms 125912 KB Output is correct
12 Correct 92 ms 125944 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 125920 KB Output is correct
2 Correct 97 ms 125816 KB Output is correct
3 Correct 98 ms 125944 KB Output is correct
4 Correct 1275 ms 145972 KB Output is correct
5 Correct 943 ms 145520 KB Output is correct
6 Correct 1427 ms 143196 KB Output is correct
7 Correct 1487 ms 142976 KB Output is correct
8 Correct 921 ms 138448 KB Output is correct
9 Correct 1430 ms 143096 KB Output is correct
10 Correct 1298 ms 142672 KB Output is correct
11 Correct 97 ms 125944 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 125816 KB Output is correct
2 Correct 100 ms 126072 KB Output is correct
3 Correct 98 ms 126072 KB Output is correct
4 Correct 98 ms 125908 KB Output is correct
5 Correct 151 ms 125944 KB Output is correct
6 Correct 95 ms 126064 KB Output is correct
7 Correct 95 ms 126020 KB Output is correct
8 Correct 96 ms 125944 KB Output is correct
9 Correct 94 ms 126072 KB Output is correct
10 Correct 96 ms 125944 KB Output is correct
11 Correct 96 ms 125880 KB Output is correct
12 Correct 1748 ms 138568 KB Output is correct
13 Correct 2600 ms 133600 KB Output is correct
14 Correct 721 ms 131320 KB Output is correct
15 Correct 2974 ms 135856 KB Output is correct
16 Correct 790 ms 138744 KB Output is correct
17 Correct 2012 ms 137592 KB Output is correct
18 Correct 3091 ms 140136 KB Output is correct
19 Correct 2627 ms 140332 KB Output is correct
20 Correct 2666 ms 139612 KB Output is correct
21 Correct 94 ms 125944 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 125820 KB Output is correct
2 Correct 96 ms 125992 KB Output is correct
3 Correct 94 ms 125948 KB Output is correct
4 Correct 94 ms 125916 KB Output is correct
5 Correct 92 ms 125816 KB Output is correct
6 Correct 93 ms 126088 KB Output is correct
7 Correct 94 ms 125992 KB Output is correct
8 Correct 93 ms 125932 KB Output is correct
9 Correct 93 ms 125944 KB Output is correct
10 Correct 93 ms 125944 KB Output is correct
11 Correct 93 ms 125944 KB Output is correct
12 Correct 1213 ms 145840 KB Output is correct
13 Correct 942 ms 145656 KB Output is correct
14 Correct 1359 ms 143188 KB Output is correct
15 Correct 1453 ms 142968 KB Output is correct
16 Correct 922 ms 138488 KB Output is correct
17 Correct 1480 ms 143080 KB Output is correct
18 Correct 1322 ms 142592 KB Output is correct
19 Correct 1808 ms 138816 KB Output is correct
20 Correct 2626 ms 133388 KB Output is correct
21 Correct 730 ms 131192 KB Output is correct
22 Correct 3005 ms 135792 KB Output is correct
23 Correct 810 ms 138664 KB Output is correct
24 Correct 1927 ms 137648 KB Output is correct
25 Correct 3050 ms 140120 KB Output is correct
26 Correct 2507 ms 140320 KB Output is correct
27 Correct 2570 ms 139536 KB Output is correct
28 Correct 1267 ms 231040 KB Output is correct
29 Correct 3081 ms 242700 KB Output is correct
30 Correct 7363 ms 201776 KB Output is correct
31 Correct 6924 ms 185384 KB Output is correct
32 Correct 826 ms 135680 KB Output is correct
33 Correct 1044 ms 136592 KB Output is correct
34 Correct 1676 ms 236516 KB Output is correct
35 Correct 2456 ms 188732 KB Output is correct
36 Correct 4800 ms 240720 KB Output is correct
37 Correct 3897 ms 240800 KB Output is correct
38 Correct 3868 ms 240148 KB Output is correct
39 Correct 3125 ms 216340 KB Output is correct
40 Correct 100 ms 125836 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 125892 KB Output is correct
2 Correct 97 ms 125996 KB Output is correct
3 Correct 96 ms 126040 KB Output is correct
4 Correct 95 ms 125944 KB Output is correct
5 Correct 94 ms 125888 KB Output is correct
6 Correct 100 ms 125956 KB Output is correct
7 Correct 93 ms 125816 KB Output is correct
8 Correct 94 ms 125896 KB Output is correct
9 Correct 94 ms 126072 KB Output is correct
10 Correct 95 ms 125968 KB Output is correct
11 Correct 94 ms 125944 KB Output is correct
12 Correct 1199 ms 145704 KB Output is correct
13 Correct 925 ms 145520 KB Output is correct
14 Correct 1356 ms 143068 KB Output is correct
15 Correct 1382 ms 142780 KB Output is correct
16 Correct 890 ms 138488 KB Output is correct
17 Correct 1431 ms 142968 KB Output is correct
18 Correct 1304 ms 142700 KB Output is correct
19 Correct 1913 ms 138544 KB Output is correct
20 Correct 2558 ms 133428 KB Output is correct
21 Correct 710 ms 131120 KB Output is correct
22 Correct 2934 ms 135632 KB Output is correct
23 Correct 749 ms 138580 KB Output is correct
24 Correct 1825 ms 137516 KB Output is correct
25 Correct 3216 ms 139984 KB Output is correct
26 Correct 2745 ms 140108 KB Output is correct
27 Correct 2470 ms 139516 KB Output is correct
28 Correct 1284 ms 230960 KB Output is correct
29 Correct 2951 ms 242644 KB Output is correct
30 Correct 7487 ms 201780 KB Output is correct
31 Correct 6742 ms 185424 KB Output is correct
32 Correct 800 ms 135672 KB Output is correct
33 Correct 1051 ms 136552 KB Output is correct
34 Correct 1593 ms 236396 KB Output is correct
35 Correct 2387 ms 188900 KB Output is correct
36 Correct 4492 ms 240716 KB Output is correct
37 Correct 3495 ms 240624 KB Output is correct
38 Correct 3614 ms 240136 KB Output is correct
39 Runtime error 963 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -