oj.uz

Submission #281833

# Submission time Handle Problem Language Result Execution time Memory
281833 2020-08-23T14:22:14 Z Saboon Game (IOI13_game) C++14
10 / 100
 2938 ms 8232 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int SQ = 150;

ll gcd2(ll X, ll Y){
    ll tmp;
    while (X != Y && Y != 0){
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ll seg[100+SQ][100+8*SQ];

ll get(int id, int L, int R, int l, int r, int block){
	if (r <= L or R <= l)
		return 0;
	if (l <= L and R <= r)
		return seg[block][id];
	int mid = (L + R) >> 1;
	return gcd2(get(2*id+0, L, mid, l, r, block),
				get(2*id+1, mid, R, l, r, block));
}

void change(int id, int L, int R, int idx, ll K, int block){
	if (idx < L or R <= idx)
		return;
	if (L + 1 == R){
		seg[block][id] = K;
		return;
	}
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, idx, K, block);
	change(2*id+1, mid, R, idx, K, block);
	seg[block][id] = gcd2(seg[block][2*id+0], seg[block][2*id+1]);
}

int numBlock;
vector<pair<pair<int,int>,ll>> a[100+SQ];
map<pair<int,int>, ll> mp;
map<pair<int,int>, int> go;
vector<pair<int,ll>> b[100+SQ];

void changeblock(int block){
	sort(a[block].begin(), a[block].end());
	for (int i = 0; i < 8*SQ; i++)
		seg[block][i] = 0;
	b[block].clear();
	for (auto it : a[block])
		b[block].push_back({it.first.second,it.second});
	sort(b[block].begin(), b[block].end());
	for (int i = 0; i < b[block].size(); i++)
		change(1, 0, b[block].size(), i, b[block][i].second, block);
}

void init(int R, int C){
	go.clear();
	for (int i = 0; i < SQ; i++)
		a[i].clear();
	int n = mp.size();
	numBlock = max((n+SQ-1)/SQ,1);
	int idx = -1;
	for (auto it : mp){
		idx ++;
		go[it.first] = idx/SQ;
		a[idx/SQ].push_back(it);
	}
	for (int i = 0; i < numBlock; i++)
		changeblock(i);
}

void update(int P, int Q, ll K){
	if (mp.count({P,Q})){
		mp[{P,Q}] = K;
		int block = go[{P,Q}];
		for (int i = 0; i < a[block].size(); i++)
			if (a[block][i].first == make_pair(P,Q))
				a[block][i].second = K;
		changeblock(block);
		return;
	}
	mp[{P,Q}] = K;
	int block = numBlock-1;
	for (int i = 1; i < numBlock; i++)
		if (P <= a[i][0].first.first)
			block = i-1;
	go[{P,Q}] = block;
	a[block].push_back({{P,Q},K});
	if (a[block].size() == 2*SQ)
		init(0,0);
	else
		changeblock(block);
}

ll calculate(int P, int Q, int U, int V){
	ll answer = 0;
	for (int i = 0; i < numBlock; i++){
		if (a[i].empty())
			continue;
		if (a[i][0].first.first > U)
			break;
		if (a[i].back().first.first < P)
			continue;
		if (a[i][0].first.first >= P and a[i].back().first.first <= U){
			int lo = lower_bound(b[i].begin(), b[i].end(), make_pair(Q,-1LL)) - b[i].begin();
			int hi = lower_bound(b[i].begin(), b[i].end(), make_pair(V+1, -1LL)) - b[i].begin();
			answer = gcd2(answer, get(1, 0, b[i].size(), lo, hi, i));
			continue;
		}
		for (auto it : a[i]){
			int p = it.first.first, q = it.first.second;
			ll x = it.second;
			if (P <= p and p <= U and Q <= q and q <= V)
				answer = gcd2(answer, x);
		}
	}
	return answer;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~
game.cpp: In function 'void changeblock(int)':
game.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < b[block].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
game.cpp: In function 'void update(int, int, ll)':
game.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 0; i < a[block].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 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 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 1884 ms 8232 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 2938 ms 8076 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1886 ms 7952 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1888 ms 7932 KB Output isn't correct
13 Halted 0 ms 0 KB -