oj.uz

Submission #135869

# Submission time Handle Problem Language Result Execution time Memory
135869 2019-07-24T12:47:45 Z mirbek01 Game (IOI13_game) C++11
37 / 100
 13000 ms 40140 KB 
#include "game.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

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

int n;
vector < vector <long long> > t;

void upd(int tp, int pos, long long val, int v = 1, int tl = 1, int tr = n){
	if(tl == tr)
		t[tp][v] = val;
	else {
		int tm = (tl + tr) >> 1;
		if(pos <= tm)
			upd(tp, pos, val, v << 1, tl, tm);
		else 
			upd(tp, pos, val, v << 1 | 1, tm + 1, tr);
		t[tp][v] = gcd2(t[tp][v << 1], t[tp][v << 1 | 1]);
	}
}

long long get(int tp, int l, int r, int v = 1, int tl = 1, int tr = n){
	if(l > tr || tl > r) 
		return 0ll;
	if(l <= tl && tr <= r)
		return t[tp][v];
	int tm = (tl + tr) >> 1;
	return gcd2(get(tp, l, r, v << 1, tl, tm), get(tp, l, r, v << 1 | 1, tm + 1, tr));
}

void init(int R, int C) {
	t.resize(R);
	n = C;
	for(int i = 0; i < R; i ++)
		t[i].resize(4 * (C + 1));
}

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

long long calculate(int P, int Q, int U, int V) {
	long long ans = 0;
	for(int i = P; i <= U; i ++)
		ans = gcd2(ans, get(i, Q + 1, V + 1));
	return ans;
}

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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 632 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1475 ms 37972 KB Output is correct
5 Correct 840 ms 40100 KB Output is correct
6 Correct 1210 ms 37408 KB Output is correct
7 Correct 1275 ms 37216 KB Output is correct
8 Correct 969 ms 37692 KB Output is correct
9 Correct 1229 ms 37252 KB Output is correct
10 Correct 1079 ms 36848 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Execution timed out 13094 ms 32936 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 360 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 1430 ms 37988 KB Output is correct
13 Correct 847 ms 39980 KB Output is correct
14 Correct 1191 ms 37672 KB Output is correct
15 Correct 1294 ms 37368 KB Output is correct
16 Correct 953 ms 37500 KB Output is correct
17 Correct 1234 ms 37280 KB Output is correct
18 Correct 1049 ms 36932 KB Output is correct
19 Execution timed out 13068 ms 33724 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 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 2 ms 636 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 1473 ms 38060 KB Output is correct
13 Correct 872 ms 40140 KB Output is correct
14 Correct 1232 ms 37340 KB Output is correct
15 Correct 1365 ms 37272 KB Output is correct
16 Correct 1093 ms 37632 KB Output is correct
17 Correct 1353 ms 37256 KB Output is correct
18 Correct 1040 ms 36940 KB Output is correct
19 Execution timed out 13098 ms 33736 KB Time limit exceeded
20 Halted 0 ms 0 KB -