oj.uz

Submission #169260

# Submission time Handle Problem Language Result Execution time Memory
169260 2019-12-19T11:20:36 Z oolimry Game (IOI13_game) C++14
36 / 100
 1395 ms 132472 KB 
#include "game.h"
#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;
}

static long long tree[4005][4005];

int N, M;
void init(int R, int C) {
	N = R; M = C;
    for(int i = 1;i <= 2 * R;i++){
		for(int j = 1;j <= 2 * C;j++){
			tree[i][j] = 0;
		}
	}
}

void update(int r, int c, long long v) {
	int nr = N + r;
	int nc = M + c;
	tree[nr][nc] = v;
	while(nr > 0){
		nc = M + c;
		while(nc > 0){
			if(nr < N){
				tree[nr][nc] = gcd2(tree[nr<<1][nc],tree[nr<<1|1][nc]);
			}
			else if(nc < M){
				tree[nr][nc] = gcd2(tree[nr][nc<<1],tree[nr][nc<<1|1]);
			}
			else tree[nr][nc] = v;
			//cout << nr << " " << nc << "\n";
			nc >>= 1;
		}
		nr >>= 1;
	}
	//cout << endl;
}

long long calculate(int t, int l, int b, int r) {
    long long ans = 0;
    b++; r++;
    for(t += N, b += N;t < b;t >>= 1, b >>= 1){
		if(t&1){
			for(int nl = l+M, nr = r+M;nl < nr;nr >>= 1, nl >>= 1){
				if(nl&1){
					ans = gcd2(ans, tree[t][nl]);
					//cout << t << " " << nl << "\n";
					nl++;
				}
				if(nr&1){
					nr--;
					ans = gcd2(ans, tree[t][nr]);
					//cout << t << " " << nr << "\n";
				}
			}
			t++;
		}
		if(b&1){
			b--;
			for(int nl = l+M, nr = r+M;nl < nr;nr >>= 1, nl >>= 1){
				if(nl&1){
					ans = gcd2(ans, tree[b][nl]);
					//cout << b << " " << nl << "\n";
					nl++;
				}
				if(nr&1){
					nr--;
					ans = gcd2(ans, tree[b][nr]);
					//cout << b << " " << nr << "\n";
				}
			}
		}
	}
	//cout << endl;
	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 504 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 1400 KB Output is correct
6 Correct 3 ms 1400 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 3 ms 1060 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 3 ms 1400 KB Output is correct
11 Correct 3 ms 1528 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 568 ms 7748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1400 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 3 ms 1400 KB Output is correct
10 Correct 3 ms 1400 KB Output is correct
11 Correct 3 ms 1400 KB Output is correct
12 Correct 818 ms 48064 KB Output is correct
13 Correct 1055 ms 44476 KB Output is correct
14 Correct 520 ms 131124 KB Output is correct
15 Correct 1350 ms 131156 KB Output is correct
16 Correct 371 ms 130680 KB Output is correct
17 Correct 1126 ms 132008 KB Output is correct
18 Correct 1395 ms 132288 KB Output is correct
19 Correct 1265 ms 132472 KB Output is correct
20 Correct 999 ms 131880 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 376 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 1400 KB Output is correct
6 Correct 3 ms 1384 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 3 ms 1400 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 3 ms 1528 KB Output is correct
12 Incorrect 582 ms 7808 KB Output isn't correct
13 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 1400 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 3 ms 1528 KB Output is correct
6 Correct 3 ms 1528 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 3 ms 1528 KB Output is correct
12 Incorrect 561 ms 7800 KB Output isn't correct
13 Halted 0 ms 0 KB -