oj.uz

Submission #121617

# Submission time Handle Problem Language Result Execution time Memory
121617 2019-06-26T20:47:07 Z yusufake Game (IOI13_game) C++
80 / 100
 7391 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 * 61 * 61;
 
int Y[N],L[N],R[N],id=1;
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 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 == 22000 * 71 * 71 - 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 == 22000 * 71 * 71 - 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) {}

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:34:21: 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:34:40: 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:39:21: 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:39:46: 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:48: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:48: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:49: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:53:35: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     if(id == 22000 * 71 * 71 - 5) while(1);
                                   ^~~~~
game.cpp:54: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:55: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:55: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:56: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 512 KB Output is correct
3 Correct 4 ms 512 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 1116 ms 27584 KB Output is correct
5 Correct 848 ms 27592 KB Output is correct
6 Correct 1280 ms 24604 KB Output is correct
7 Correct 1326 ms 24384 KB Output is correct
8 Correct 862 ms 15628 KB Output is correct
9 Correct 1344 ms 24824 KB Output is correct
10 Correct 1180 ms 24148 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 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 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1656 ms 12536 KB Output is correct
13 Correct 2497 ms 6072 KB Output is correct
14 Correct 613 ms 1144 KB Output is correct
15 Correct 2782 ms 9024 KB Output is correct
16 Correct 656 ms 14704 KB Output is correct
17 Correct 1721 ms 10996 KB Output is correct
18 Correct 2743 ms 15008 KB Output is correct
19 Correct 2465 ms 15140 KB Output is correct
20 Correct 2254 ms 14408 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 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 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 7 ms 640 KB Output is correct
10 Correct 3 ms 456 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1190 ms 27360 KB Output is correct
13 Correct 862 ms 27840 KB Output is correct
14 Correct 1375 ms 24700 KB Output is correct
15 Correct 1279 ms 24504 KB Output is correct
16 Correct 799 ms 15404 KB Output is correct
17 Correct 1318 ms 24620 KB Output is correct
18 Correct 1155 ms 24184 KB Output is correct
19 Correct 1757 ms 12748 KB Output is correct
20 Correct 2501 ms 6060 KB Output is correct
21 Correct 622 ms 1104 KB Output is correct
22 Correct 2884 ms 8992 KB Output is correct
23 Correct 690 ms 14756 KB Output is correct
24 Correct 1811 ms 10976 KB Output is correct
25 Correct 2957 ms 14864 KB Output is correct
26 Correct 2655 ms 15236 KB Output is correct
27 Correct 2394 ms 14520 KB Output is correct
28 Correct 1184 ms 157584 KB Output is correct
29 Correct 2913 ms 175944 KB Output is correct
30 Correct 7269 ms 119952 KB Output is correct
31 Correct 6608 ms 91716 KB Output is correct
32 Correct 694 ms 1284 KB Output is correct
33 Correct 927 ms 2940 KB Output is correct
34 Correct 1540 ms 172924 KB Output is correct
35 Correct 2145 ms 88120 KB Output is correct
36 Correct 4197 ms 173508 KB Output is correct
37 Correct 3360 ms 173432 KB Output is correct
38 Correct 3335 ms 172856 KB Output is correct
39 Correct 2922 ms 133272 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 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 4 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1153 ms 27508 KB Output is correct
13 Correct 840 ms 27568 KB Output is correct
14 Correct 1286 ms 24700 KB Output is correct
15 Correct 1352 ms 24292 KB Output is correct
16 Correct 788 ms 15580 KB Output is correct
17 Correct 1300 ms 24568 KB Output is correct
18 Correct 1279 ms 24052 KB Output is correct
19 Correct 1683 ms 12592 KB Output is correct
20 Correct 2537 ms 6008 KB Output is correct
21 Correct 658 ms 1144 KB Output is correct
22 Correct 2882 ms 9052 KB Output is correct
23 Correct 949 ms 14612 KB Output is correct
24 Correct 1709 ms 10740 KB Output is correct
25 Correct 2770 ms 14760 KB Output is correct
26 Correct 2398 ms 15096 KB Output is correct
27 Correct 2353 ms 14524 KB Output is correct
28 Correct 1197 ms 157688 KB Output is correct
29 Correct 2962 ms 175968 KB Output is correct
30 Correct 7391 ms 120136 KB Output is correct
31 Correct 6913 ms 91752 KB Output is correct
32 Correct 686 ms 1244 KB Output is correct
33 Correct 913 ms 2936 KB Output is correct
34 Correct 1565 ms 173020 KB Output is correct
35 Correct 2261 ms 88180 KB Output is correct
36 Correct 4219 ms 173488 KB Output is correct
37 Correct 3384 ms 173648 KB Output is correct
38 Correct 3397 ms 172876 KB Output is correct
39 Runtime error 1217 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -