oj.uz

Submission #169263

# Submission time Handle Problem Language Result Execution time Memory
169263 2019-12-19T11:33:25 Z oolimry Game (IOI13_game) C++14
37 / 100
 13000 ms 250204 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;
}
typedef pair<int,int> ii;

struct pair_hash
{
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const
    {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};

static map<ii, long long> tree;

int N, M;
void init(int R, int C) {
	N = R; M = C;
    return;
}

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

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[ii(t,nl)]);
					//cout << t << " " << nl << "\n";
					nl++;
				}
				if(nr&1){
					nr--;
					ans = gcd2(ans, tree[ii(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[ii(b,nl)]);
					//cout << b << " " << nl << "\n";
					nl++;
				}
				if(nr&1){
					nr--;
					ans = gcd2(ans, tree[ii(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 252 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 760 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 2 ms 256 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 4161 ms 39160 KB Output is correct
5 Correct 2219 ms 34388 KB Output is correct
6 Correct 5504 ms 94264 KB Output is correct
7 Correct 5542 ms 93960 KB Output is correct
8 Correct 4299 ms 90532 KB Output is correct
9 Correct 5205 ms 96308 KB Output is correct
10 Correct 5081 ms 93680 KB Output is correct
11 Correct 2 ms 256 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 5 ms 760 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 760 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 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 6510 ms 44252 KB Output is correct
13 Correct 4423 ms 16512 KB Output is correct
14 Correct 4119 ms 2944 KB Output is correct
15 Correct 5676 ms 24636 KB Output is correct
16 Correct 2045 ms 62004 KB Output is correct
17 Execution timed out 13095 ms 246792 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 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 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 4127 ms 39144 KB Output is correct
13 Correct 2194 ms 34368 KB Output is correct
14 Correct 5201 ms 94148 KB Output is correct
15 Correct 5272 ms 93872 KB Output is correct
16 Correct 4469 ms 90364 KB Output is correct
17 Correct 5503 ms 96224 KB Output is correct
18 Correct 5164 ms 93564 KB Output is correct
19 Correct 6642 ms 47120 KB Output is correct
20 Correct 4398 ms 20392 KB Output is correct
21 Correct 4202 ms 7532 KB Output is correct
22 Correct 5660 ms 28932 KB Output is correct
23 Correct 2101 ms 66404 KB Output is correct
24 Execution timed out 13018 ms 250204 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 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 4062 ms 39120 KB Output is correct
13 Correct 2245 ms 34296 KB Output is correct
14 Correct 5484 ms 94024 KB Output is correct
15 Correct 5152 ms 93856 KB Output is correct
16 Correct 4337 ms 90512 KB Output is correct
17 Correct 5252 ms 96428 KB Output is correct
18 Correct 5481 ms 93620 KB Output is correct
19 Correct 6563 ms 47164 KB Output is correct
20 Correct 4413 ms 20660 KB Output is correct
21 Correct 4124 ms 7660 KB Output is correct
22 Correct 5741 ms 28816 KB Output is correct
23 Correct 2013 ms 66460 KB Output is correct
24 Execution timed out 13022 ms 241672 KB Time limit exceeded
25 Halted 0 ms 0 KB -