oj.uz

Submission #121654

# Submission time Handle Problem Language Result Execution time Memory
121654 2019-06-26T22:34:03 Z yusufake Game (IOI13_game) C++
80 / 100
 13000 ms 235992 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 175 ms 228088 KB Output is correct
2 Correct 176 ms 228088 KB Output is correct
3 Correct 174 ms 228088 KB Output is correct
4 Correct 172 ms 228224 KB Output is correct
5 Correct 169 ms 228004 KB Output is correct
6 Correct 177 ms 228048 KB Output is correct
7 Correct 172 ms 228080 KB Output is correct
8 Correct 185 ms 228092 KB Output is correct
9 Correct 173 ms 228216 KB Output is correct
10 Correct 170 ms 228088 KB Output is correct
11 Correct 175 ms 228180 KB Output is correct
12 Correct 177 ms 228064 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 228088 KB Output is correct
2 Correct 167 ms 228088 KB Output is correct
3 Correct 173 ms 228064 KB Output is correct
4 Correct 1303 ms 233300 KB Output is correct
5 Correct 1047 ms 233660 KB Output is correct
6 Correct 1451 ms 230520 KB Output is correct
7 Correct 1476 ms 230316 KB Output is correct
8 Correct 972 ms 231032 KB Output is correct
9 Correct 1570 ms 230468 KB Output is correct
10 Correct 1406 ms 230004 KB Output is correct
11 Correct 168 ms 228088 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 228088 KB Output is correct
2 Correct 176 ms 228160 KB Output is correct
3 Correct 172 ms 228032 KB Output is correct
4 Correct 172 ms 228216 KB Output is correct
5 Correct 169 ms 228088 KB Output is correct
6 Correct 179 ms 228188 KB Output is correct
7 Correct 175 ms 228000 KB Output is correct
8 Correct 176 ms 228088 KB Output is correct
9 Correct 180 ms 228088 KB Output is correct
10 Correct 175 ms 228088 KB Output is correct
11 Correct 223 ms 228192 KB Output is correct
12 Correct 1924 ms 233236 KB Output is correct
13 Correct 2672 ms 230208 KB Output is correct
14 Correct 862 ms 230000 KB Output is correct
15 Correct 3201 ms 230280 KB Output is correct
16 Correct 865 ms 230124 KB Output is correct
17 Correct 2150 ms 230972 KB Output is correct
18 Correct 3155 ms 230456 KB Output is correct
19 Correct 2840 ms 230848 KB Output is correct
20 Correct 2669 ms 230320 KB Output is correct
21 Correct 178 ms 228088 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 228088 KB Output is correct
2 Correct 178 ms 228088 KB Output is correct
3 Correct 182 ms 228132 KB Output is correct
4 Correct 175 ms 228108 KB Output is correct
5 Correct 183 ms 228088 KB Output is correct
6 Correct 172 ms 228020 KB Output is correct
7 Correct 173 ms 228024 KB Output is correct
8 Correct 169 ms 228120 KB Output is correct
9 Correct 172 ms 228120 KB Output is correct
10 Correct 177 ms 228092 KB Output is correct
11 Correct 173 ms 228088 KB Output is correct
12 Correct 1263 ms 233472 KB Output is correct
13 Correct 994 ms 233532 KB Output is correct
14 Correct 1440 ms 230652 KB Output is correct
15 Correct 1390 ms 230344 KB Output is correct
16 Correct 974 ms 231360 KB Output is correct
17 Correct 1621 ms 230340 KB Output is correct
18 Correct 1410 ms 230104 KB Output is correct
19 Correct 1862 ms 233756 KB Output is correct
20 Correct 2721 ms 230156 KB Output is correct
21 Correct 797 ms 230068 KB Output is correct
22 Correct 3118 ms 230360 KB Output is correct
23 Correct 840 ms 230248 KB Output is correct
24 Correct 1877 ms 230984 KB Output is correct
25 Correct 3161 ms 230824 KB Output is correct
26 Correct 2943 ms 230892 KB Output is correct
27 Correct 2680 ms 230492 KB Output is correct
28 Correct 1180 ms 230776 KB Output is correct
29 Correct 2903 ms 234100 KB Output is correct
30 Correct 7465 ms 231324 KB Output is correct
31 Correct 7262 ms 231416 KB Output is correct
32 Correct 851 ms 231160 KB Output is correct
33 Correct 1070 ms 231200 KB Output is correct
34 Correct 1567 ms 231400 KB Output is correct
35 Correct 2186 ms 232116 KB Output is correct
36 Correct 4142 ms 231864 KB Output is correct
37 Correct 3404 ms 231948 KB Output is correct
38 Correct 3405 ms 231016 KB Output is correct
39 Correct 2911 ms 231404 KB Output is correct
40 Correct 176 ms 228088 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 228076 KB Output is correct
2 Correct 171 ms 228088 KB Output is correct
3 Correct 171 ms 228088 KB Output is correct
4 Correct 176 ms 228144 KB Output is correct
5 Correct 176 ms 228128 KB Output is correct
6 Correct 169 ms 228148 KB Output is correct
7 Correct 168 ms 228044 KB Output is correct
8 Correct 185 ms 228076 KB Output is correct
9 Correct 176 ms 228088 KB Output is correct
10 Correct 170 ms 228060 KB Output is correct
11 Correct 173 ms 228104 KB Output is correct
12 Correct 1300 ms 233568 KB Output is correct
13 Correct 1054 ms 233976 KB Output is correct
14 Correct 1433 ms 230808 KB Output is correct
15 Correct 1496 ms 230344 KB Output is correct
16 Correct 1016 ms 231164 KB Output is correct
17 Correct 1489 ms 230464 KB Output is correct
18 Correct 1322 ms 229964 KB Output is correct
19 Correct 1867 ms 233596 KB Output is correct
20 Correct 2748 ms 230280 KB Output is correct
21 Correct 812 ms 230008 KB Output is correct
22 Correct 3049 ms 230368 KB Output is correct
23 Correct 875 ms 230264 KB Output is correct
24 Correct 1919 ms 230792 KB Output is correct
25 Correct 3104 ms 230568 KB Output is correct
26 Correct 2764 ms 230748 KB Output is correct
27 Correct 2497 ms 230144 KB Output is correct
28 Correct 1162 ms 230708 KB Output is correct
29 Correct 2900 ms 233812 KB Output is correct
30 Correct 7377 ms 230892 KB Output is correct
31 Correct 6711 ms 230856 KB Output is correct
32 Correct 860 ms 230620 KB Output is correct
33 Correct 1086 ms 230744 KB Output is correct
34 Correct 1605 ms 230028 KB Output is correct
35 Correct 2218 ms 231412 KB Output is correct
36 Correct 4127 ms 231288 KB Output is correct
37 Correct 3489 ms 231356 KB Output is correct
38 Correct 3256 ms 230400 KB Output is correct
39 Execution timed out 13078 ms 235992 KB Time limit exceeded
40 Halted 0 ms 0 KB -