oj.uz

Submission #349646

# Submission time Handle Problem Language Result Execution time Memory
349646 2021-01-18T05:29:31 Z tengiz05 Game (IOI13_game) C++17
63 / 100
 899 ms 256004 KB 
#include "game.h"
#ifndef EVAL
#include "grader.c"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y) {
	ll tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}
ll n, m;
vector<vector<ll>> t;
ll get(int x1, int y1, int x2, int y2){
	ll res = 0;
	for(x1+=n,x2+=n; x1<=x2; x1>>=1,x2>>=1){
		if(x1&1){
			for(int l=y1+m,r=y2+m; l<=r; l>>=1,r>>=1){
				if(l&1)res = gcd2(res, t[x1][l++]);
				if(!(r&1))res = gcd2(res, t[x1][r--]);
			}
			x1++;
		}if(!(x2&1)){
			for(int l=y1+m,r=y2+m; l<=r; l>>=1,r>>=1){
				if(l&1)res = gcd2(res, t[x2][l++]);
				if(!(r&1))res = gcd2(res, t[x2][r--]);
			}
			x2--;
		}
	}return res;
}

void upd(int x, int y, ll val){
	for(x+=n; x>=1; x>>=1){
		int i = y+m;
		for(; i>0; i>>=1){
			if(x>=n&&i>=m)t[x][i] = val;
			else if(i>=m)t[x][i] = gcd2(t[x<<1][i],t[x<<1|1][i]);
			t[x][i>>1] = gcd2(t[x][i], t[x][i^1]);
		}
	}
}

void init(int R, int C) {
	n = R, m = C;
	t.assign(n*2,vector<ll>(m*2,0));
}

void update(int P, int Q, long long K) {
	upd(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
	return get(P, Q, U, V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 407 ms 35792 KB Output is correct
5 Correct 308 ms 35976 KB Output is correct
6 Correct 414 ms 33260 KB Output is correct
7 Correct 402 ms 33260 KB Output is correct
8 Correct 343 ms 33636 KB Output is correct
9 Correct 411 ms 33260 KB Output is correct
10 Correct 364 ms 33260 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 583 ms 35820 KB Output is correct
13 Correct 626 ms 32748 KB Output is correct
14 Correct 441 ms 126360 KB Output is correct
15 Correct 818 ms 126512 KB Output is correct
16 Correct 304 ms 126444 KB Output is correct
17 Correct 767 ms 127084 KB Output is correct
18 Correct 893 ms 126828 KB Output is correct
19 Correct 876 ms 126956 KB Output is correct
20 Correct 822 ms 126500 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 411 ms 35664 KB Output is correct
13 Correct 305 ms 36184 KB Output is correct
14 Correct 404 ms 33260 KB Output is correct
15 Correct 411 ms 33260 KB Output is correct
16 Correct 343 ms 33360 KB Output is correct
17 Correct 414 ms 33388 KB Output is correct
18 Correct 362 ms 33260 KB Output is correct
19 Correct 583 ms 36332 KB Output is correct
20 Correct 628 ms 33004 KB Output is correct
21 Correct 449 ms 126956 KB Output is correct
22 Correct 812 ms 127212 KB Output is correct
23 Correct 308 ms 127084 KB Output is correct
24 Correct 779 ms 127680 KB Output is correct
25 Correct 899 ms 127468 KB Output is correct
26 Correct 881 ms 126956 KB Output is correct
27 Correct 821 ms 126316 KB Output is correct
28 Runtime error 141 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 1 ms 364 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 414 ms 35712 KB Output is correct
13 Correct 311 ms 36068 KB Output is correct
14 Correct 406 ms 33260 KB Output is correct
15 Correct 415 ms 33260 KB Output is correct
16 Correct 359 ms 33616 KB Output is correct
17 Correct 402 ms 33260 KB Output is correct
18 Correct 360 ms 33260 KB Output is correct
19 Correct 589 ms 35924 KB Output is correct
20 Correct 629 ms 32620 KB Output is correct
21 Correct 445 ms 126316 KB Output is correct
22 Correct 808 ms 126572 KB Output is correct
23 Correct 307 ms 126480 KB Output is correct
24 Correct 771 ms 127148 KB Output is correct
25 Correct 897 ms 126956 KB Output is correct
26 Correct 876 ms 126956 KB Output is correct
27 Correct 816 ms 126444 KB Output is correct
28 Runtime error 146 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -