oj.uz

Submission #137355

# Submission time Handle Problem Language Result Execution time Memory
137355 2019-07-27T13:37:49 Z TuGSGeReL Game (IOI13_game) C++17
63 / 100
 9794 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
 
int rr, cc;
unordered_map <int, unordered_map<int, ll> > sgx;
 
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int which(int node, int l, int r, int idx)
{
	if ( l == r )
	{
		return node;
	}
	
	int mid = (l + r) >> 1;
	
	if ( mid >= idx )
		which(node << 1, l, mid, idx);
	
	else
		which((node << 1) + 1, mid + 1, r, idx);
}
 
void init(int R, int C) {
	rr = R;
	cc = C;
}
 
void updy(int node, int l, int r, int idx, ll d, int whi)
{
	if ( l == r && r == idx )
	{
		sgx[whi][node] = d;
		
		do{
			whi >>= 1;
			sgx[whi][node] = gcd2(sgx[whi << 1][node], sgx[(whi << 1) + 1][node]);
		}while(whi > 1);
		
		return;
	}
	
	int mid = (l + r) >> 1;
	
	if ( idx <= mid )
		updy(node << 1, l, mid, idx, d, whi);
	
	else
		updy((node << 1) + 1, mid + 1, r, idx, d, whi);
	
	sgx[whi][node] = gcd2(sgx[whi][node << 1], sgx[whi][(node << 1) + 1]);
	
	do{
		whi >>= 1;
		sgx[whi][node] = gcd2(sgx[whi << 1][node], sgx[(whi << 1) + 1][node]);
	}while(whi > 1);
}
 
 
ll lqu(int node, int l, int r, int L, int R, int whi)
{
	if ( l > R || r < L )
		return 0;
		
	if ( l >= L && r <= R )
		return sgx[whi][node];
	
	int mid = (l + r) >> 1;
	
	return gcd2(lqu(node << 1, l, mid, L, R, whi), lqu((node << 1) + 1, mid + 1, r, L, R, whi));
}
 
ll query (int node, int l, int r, int lx, int ly, int rx, int ry)
{
	if ( l > rx || r < lx )
		return 0;
	
	if ( l >= lx && r <= rx )
		return lqu(1, 1, cc, ly, ry, node);
	
	int mid = (l + r) >> 1;
	
	return gcd2(query(node << 1, l, mid, lx, ly, rx, ry), query((node << 1) + 1, mid + 1, r, lx, ly, rx, ry));
}
 
void update(int P, int Q, ll K) {
	updy(1, 1, cc, Q + 1, K, which(1, 1, rr, P + 1));
}
 
ll calculate(int P, int Q, int U, int V) {
	return query(1, 1, rr, P + 1, Q + 1, U + 1, V + 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 'int which(int, int, int, int)':
game.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 636 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3139 ms 31644 KB Output is correct
5 Correct 1924 ms 28792 KB Output is correct
6 Correct 3345 ms 71672 KB Output is correct
7 Correct 3617 ms 71608 KB Output is correct
8 Correct 2692 ms 69312 KB Output is correct
9 Correct 3399 ms 72128 KB Output is correct
10 Correct 3104 ms 71296 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 636 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 4003 ms 35880 KB Output is correct
13 Correct 5044 ms 16580 KB Output is correct
14 Correct 2637 ms 6140 KB Output is correct
15 Correct 6844 ms 22976 KB Output is correct
16 Correct 993 ms 47224 KB Output is correct
17 Correct 8398 ms 173712 KB Output is correct
18 Correct 9794 ms 187844 KB Output is correct
19 Correct 9440 ms 187768 KB Output is correct
20 Correct 8879 ms 187180 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 708 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3004 ms 31900 KB Output is correct
13 Correct 1933 ms 28540 KB Output is correct
14 Correct 3385 ms 71272 KB Output is correct
15 Correct 3313 ms 71124 KB Output is correct
16 Correct 2800 ms 69044 KB Output is correct
17 Correct 3497 ms 71844 KB Output is correct
18 Correct 3097 ms 70936 KB Output is correct
19 Correct 4088 ms 35520 KB Output is correct
20 Correct 5101 ms 16372 KB Output is correct
21 Correct 2656 ms 5748 KB Output is correct
22 Correct 6752 ms 22576 KB Output is correct
23 Correct 1014 ms 46956 KB Output is correct
24 Correct 8071 ms 173316 KB Output is correct
25 Correct 9557 ms 187656 KB Output is correct
26 Correct 9388 ms 187868 KB Output is correct
27 Correct 9201 ms 186864 KB Output is correct
28 Runtime error 1788 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 636 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3029 ms 32216 KB Output is correct
13 Correct 2044 ms 28992 KB Output is correct
14 Correct 3370 ms 71700 KB Output is correct
15 Correct 3361 ms 71472 KB Output is correct
16 Correct 2698 ms 69372 KB Output is correct
17 Correct 3556 ms 72344 KB Output is correct
18 Correct 3263 ms 71336 KB Output is correct
19 Correct 4124 ms 35912 KB Output is correct
20 Correct 5112 ms 16684 KB Output is correct
21 Correct 2629 ms 6160 KB Output is correct
22 Correct 6905 ms 22772 KB Output is correct
23 Correct 1016 ms 47156 KB Output is correct
24 Correct 7847 ms 173928 KB Output is correct
25 Correct 9348 ms 188180 KB Output is correct
26 Correct 9364 ms 188220 KB Output is correct
27 Correct 8990 ms 187408 KB Output is correct
28 Runtime error 1821 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -