oj.uz

Submission #298142

# Submission time Handle Problem Language Result Execution time Memory
298142 2020-09-12T12:38:33 Z williamMBDK Game (IOI13_game) C++11
37 / 100
 13000 ms 40376 KB 
#include<bits/stdc++.h>
#include "game.h"
#define int long long
using namespace std;

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;
}

struct ST{
	vector<int> arr;
	ST(){}
	ST(int N){
		arr = vector<int> (4 * N);
	}
	int u(int idx, int l, int r, int qidx, int qval){
		if(r < qidx || l > qidx) return arr[idx];
		if(l == r && qidx == l){
			arr[idx] = qval;
			return arr[idx];
		}
		int m = (l + r) / 2;
		arr[idx] = gcd2(u(idx * 2, l, m, qidx, qval), u(idx * 2 + 1, m + 1, r, qidx, qval));
		// cout << arr[idx] << " " << l << " " << r << endl;
		return arr[idx];
	}	
	int q(int idx, int l, int r, int ql, int qr){
		if(l > qr || r < ql) return 0;
		if(l >= ql && r <= qr) return arr[idx];
		int m = (l + r) / 2;
		return gcd2(q(idx * 2, l, m, ql, qr), q(idx * 2 + 1, m + 1, r, ql, qr));
	}
};

int R, C;
vector<ST> sts;

void init(signed _R, signed _C) {
	R = _R;
	C = _C;
	sts = vector<ST> (R, ST(C));
}

void update(signed P, signed Q, int K) {
	sts[P].u(1,0,C-1,Q,K);
}

long long calculate(signed P, signed Q, signed U, signed V) {
	int res = 0;
	for(int i = P; i <= U; i++){
		res = gcd2(res, sts[i].q(1,0,C-1,Q,V));
	}
	return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1 ms 256 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 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1070 ms 40252 KB Output is correct
5 Correct 597 ms 40068 KB Output is correct
6 Correct 988 ms 37452 KB Output is correct
7 Correct 1031 ms 37512 KB Output is correct
8 Correct 922 ms 37692 KB Output is correct
9 Correct 1033 ms 37304 KB Output is correct
10 Correct 951 ms 36920 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 372 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Execution timed out 13024 ms 34120 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 372 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1053 ms 40376 KB Output is correct
13 Correct 595 ms 40124 KB Output is correct
14 Correct 1002 ms 37432 KB Output is correct
15 Correct 1020 ms 37308 KB Output is correct
16 Correct 897 ms 37852 KB Output is correct
17 Correct 1016 ms 37560 KB Output is correct
18 Correct 965 ms 36920 KB Output is correct
19 Execution timed out 13096 ms 34124 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 672 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 640 KB Output is correct
12 Correct 1086 ms 40248 KB Output is correct
13 Correct 606 ms 40212 KB Output is correct
14 Correct 1026 ms 37360 KB Output is correct
15 Correct 1087 ms 37180 KB Output is correct
16 Correct 928 ms 37600 KB Output is correct
17 Correct 1108 ms 37392 KB Output is correct
18 Correct 987 ms 36980 KB Output is correct
19 Execution timed out 13025 ms 33956 KB Time limit exceeded
20 Halted 0 ms 0 KB -