oj.uz

Submission #292577

# Submission time Handle Problem Language Result Execution time Memory
292577 2020-09-07T09:55:42 Z crossing0ver Game (IOI13_game) C++17
80 / 100
 5946 ms 256000 KB 
#include<bits/stdc++.h>
#define ll long long 
#define tree int v,int tl,int tr
#define tm (tl + tr >> 1)
#define lhs L[v],tl,tm
#define rhs R[v], tm+1,tr
#include "game.h"
 
 
using namespace std;
const int N = 2E7;
 
int L[N],R[N],A[N],id = 1,posx,posy, lx,ly,rx,ry;
ll ans[N],val;
ll get_y (tree) {
	if (tr < ly || tl > ry || !v) return 0;
	if (tl >= ly && tr <= ry) {
		return ans[v];
	}
	return __gcd ( get_y(lhs),get_y(rhs));	
	
}
ll get_x (tree) {
	if (tr < lx || tl > rx ) return 0;
	if (tl >= lx && tr <= rx) {
		if (!A[v]) return 0;
		return get_y(A[v],0,1e9);
	}
	return __gcd ( get_x (lhs), get_x(rhs));
}
void up_y(tree,int a,int b,bool flag) {
	if (tl == tr)	{
		if (flag) ans[v] = val;
		else ans[v] = __gcd(ans[a],ans[b]);
		return;
	}
	if (posy <= tm) {
		if (!L[v]) L[v] = ++id;
		up_y(lhs,L[a],L[b],flag);
	}
	else {
		if (!R[v]) R[v] = ++id;
		up_y(rhs,R[a],R[b],flag);
	}
	ans[v] = __gcd(ans[ L[v] ],ans[ R[v] ]);
}
void up_x(tree) {
	 if (tl < tr) {
	 	if (posx <= tm) {
	 		if (!L[v]) L[v] = ++id;
	 		up_x(lhs);
		 }
		 else {
		 	if (!R[v]) R[v] = ++id;
	 		up_x(rhs);
		 }
	 }
	 if (!A[v]) A[v] = ++id;
	 up_y(A[ v ],0,1e9,A[ L[v] ], A[ R[v] ],tl == tr); 
}
void update(int x, int y, ll t){
	posx = x;
	posy = y;
	val = t;
	up_x(1,0,1e9);
}
ll calculate(int a, int b, int a2, int b2){
	lx = a; ly = b;
	rx = a2; ry = b2;
	return get_x(1,0,1e9);
}	
void init(int a, int b) {}

Compilation message

grader.c: In function 'int main()':
grader.c:25:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   25 |     while(res != 1);
      |     ^~~~~
grader.c:26:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   26 |  res = fscanf(f, "%d", &C);
      |  ^~~
grader.c:27:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   27 |     while(res != 1);
      |     ^~~~~
grader.c:28:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   28 |  res = fscanf(f, "%d", &N);
      |  ^~~
game.cpp: In function 'long long int get_y(int, int, int)':
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:5:21: note: in expansion of macro 'tm'
    5 | #define lhs L[v],tl,tm
      |                     ^~
game.cpp:20:23: note: in expansion of macro 'lhs'
   20 |  return __gcd ( get_y(lhs),get_y(rhs));
      |                       ^~~
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:6:19: note: in expansion of macro 'tm'
    6 | #define rhs R[v], tm+1,tr
      |                   ^~
game.cpp:20:34: note: in expansion of macro 'rhs'
   20 |  return __gcd ( get_y(lhs),get_y(rhs));
      |                                  ^~~
game.cpp: In function 'long long int get_x(int, int, int)':
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:5:21: note: in expansion of macro 'tm'
    5 | #define lhs L[v],tl,tm
      |                     ^~
game.cpp:29:24: note: in expansion of macro 'lhs'
   29 |  return __gcd ( get_x (lhs), get_x(rhs));
      |                        ^~~
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:6:19: note: in expansion of macro 'tm'
    6 | #define rhs R[v], tm+1,tr
      |                   ^~
game.cpp:29:36: note: in expansion of macro 'rhs'
   29 |  return __gcd ( get_x (lhs), get_x(rhs));
      |                                    ^~~
game.cpp: In function 'void up_y(int, int, int, int, int, bool)':
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:37:14: note: in expansion of macro 'tm'
   37 |  if (posy <= tm) {
      |              ^~
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:5:21: note: in expansion of macro 'tm'
    5 | #define lhs L[v],tl,tm
      |                     ^~
game.cpp:39:8: note: in expansion of macro 'lhs'
   39 |   up_y(lhs,L[a],L[b],flag);
      |        ^~~
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:6:19: note: in expansion of macro 'tm'
    6 | #define rhs R[v], tm+1,tr
      |                   ^~
game.cpp:43:8: note: in expansion of macro 'rhs'
   43 |   up_y(rhs,R[a],R[b],flag);
      |        ^~~
game.cpp: In function 'void up_x(int, int, int)':
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:49:16: note: in expansion of macro 'tm'
   49 |    if (posx <= tm) {
      |                ^~
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:5:21: note: in expansion of macro 'tm'
    5 | #define lhs L[v],tl,tm
      |                     ^~
game.cpp:51:10: note: in expansion of macro 'lhs'
   51 |     up_x(lhs);
      |          ^~~
game.cpp:4:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    4 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
game.cpp:6:19: note: in expansion of macro 'tm'
    6 | #define rhs R[v], tm+1,tr
      |                   ^~
game.cpp:55:10: note: in expansion of macro 'rhs'
   55 |     up_x(rhs);
      |          ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1307 ms 28528 KB Output is correct
5 Correct 828 ms 28792 KB Output is correct
6 Correct 1235 ms 25652 KB Output is correct
7 Correct 1161 ms 25464 KB Output is correct
8 Correct 859 ms 16632 KB Output is correct
9 Correct 1268 ms 25708 KB Output is correct
10 Correct 1198 ms 25188 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 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 1 ms 372 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1689 ms 13792 KB Output is correct
13 Correct 2317 ms 7160 KB Output is correct
14 Correct 689 ms 2296 KB Output is correct
15 Correct 2449 ms 10084 KB Output is correct
16 Correct 728 ms 15736 KB Output is correct
17 Correct 1788 ms 11928 KB Output is correct
18 Correct 2857 ms 15900 KB Output is correct
19 Correct 2456 ms 16164 KB Output is correct
20 Correct 2202 ms 15556 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 544 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1061 ms 28536 KB Output is correct
13 Correct 916 ms 28836 KB Output is correct
14 Correct 1056 ms 25660 KB Output is correct
15 Correct 1191 ms 25444 KB Output is correct
16 Correct 762 ms 16632 KB Output is correct
17 Correct 1236 ms 25704 KB Output is correct
18 Correct 1242 ms 25192 KB Output is correct
19 Correct 1637 ms 13716 KB Output is correct
20 Correct 2151 ms 7104 KB Output is correct
21 Correct 737 ms 2424 KB Output is correct
22 Correct 2525 ms 10016 KB Output is correct
23 Correct 787 ms 15740 KB Output is correct
24 Correct 1642 ms 11940 KB Output is correct
25 Correct 2592 ms 16000 KB Output is correct
26 Correct 2352 ms 16216 KB Output is correct
27 Correct 2271 ms 15608 KB Output is correct
28 Correct 1248 ms 168168 KB Output is correct
29 Correct 2648 ms 185936 KB Output is correct
30 Correct 5946 ms 126988 KB Output is correct
31 Correct 5436 ms 98768 KB Output is correct
32 Correct 798 ms 10360 KB Output is correct
33 Correct 869 ms 11896 KB Output is correct
34 Correct 1178 ms 179780 KB Output is correct
35 Correct 2178 ms 97828 KB Output is correct
36 Correct 3778 ms 183968 KB Output is correct
37 Correct 3104 ms 184092 KB Output is correct
38 Correct 3145 ms 183396 KB Output is correct
39 Correct 2703 ms 143520 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 488 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1006 ms 27464 KB Output is correct
13 Correct 929 ms 27596 KB Output is correct
14 Correct 1054 ms 24508 KB Output is correct
15 Correct 1342 ms 24320 KB Output is correct
16 Correct 750 ms 15608 KB Output is correct
17 Correct 1226 ms 24424 KB Output is correct
18 Correct 1164 ms 23992 KB Output is correct
19 Correct 1743 ms 12664 KB Output is correct
20 Correct 2141 ms 6008 KB Output is correct
21 Correct 719 ms 1048 KB Output is correct
22 Correct 2591 ms 9060 KB Output is correct
23 Correct 735 ms 14520 KB Output is correct
24 Correct 1616 ms 10744 KB Output is correct
25 Correct 2568 ms 14812 KB Output is correct
26 Correct 2331 ms 14980 KB Output is correct
27 Correct 2290 ms 14464 KB Output is correct
28 Correct 1206 ms 157564 KB Output is correct
29 Correct 2852 ms 185964 KB Output is correct
30 Correct 5713 ms 126840 KB Output is correct
31 Correct 5667 ms 98548 KB Output is correct
32 Correct 754 ms 10376 KB Output is correct
33 Correct 924 ms 11928 KB Output is correct
34 Correct 1240 ms 179716 KB Output is correct
35 Correct 2041 ms 97784 KB Output is correct
36 Correct 3885 ms 183876 KB Output is correct
37 Correct 3108 ms 183968 KB Output is correct
38 Correct 3027 ms 183424 KB Output is correct
39 Runtime error 1141 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -