oj.uz

Submission #123794

# Submission time Handle Problem Language Result Execution time Memory
123794 2019-07-02T06:59:52 Z Mahdi_Jfri Game (IOI13_game) C++14
10 / 100
 13000 ms 6960 KB 
//#include "grader.h"
#include "game.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e4 + 20;
const int maxb = 15;
const int sq = 100;

int sz;

int x[maxn] , y[maxn] , tmp[maxn] , seg[maxb][maxn] , where[maxb][maxn];
ll g[maxb][maxn * 4] , val[maxn];

vector<int> cmpx;

map<pair<int , int> , int> MP;

bool cmpy(int a , int b)
{
	return y[a] < y[b];
}

void build(int s = 0 , int e = cmpx.size() , int h = 0)
{
	if(e - s < 2)
	{
		seg[h][s] = tmp[s];
		where[h][tmp[s]] = s;
		return;
	}

	int m = (s + e) / 2;
	build(s , m , h + 1);
	build(m , e , h + 1);

	merge(seg[h + 1] + s , seg[h + 1] + m , seg[h + 1] + m , seg[h + 1] + e , seg[h] + s , cmpy);
	for(int i = s; i < e; i++)
		where[h][seg[h][i]] = i;
}

void buildgcd(int h , int s = 0 , int e = cmpx.size() , int v = 1)
{
	if(e - s < 2)
	{
		g[h][v] = val[seg[h][s]];
		return;
	}

	int m = (s + e) / 2;
	buildgcd(h , s , m , 2 * v);
	buildgcd(h , m , e , 2 * v + 1);

	g[h][v] = __gcd(g[h][2 * v] , g[h][2 * v + 1]);
}

void updategcd(int p , int h , int s = 0 , int e = cmpx.size() , int v = 1)
{
	if(e - s < 2)
	{
		g[h][v] = val[seg[h][s]];
		return;
	}

	int m = (s + e) / 2;
	if(p < m)
		updategcd(p , h , s , m , 2 * v);
	else
		updategcd(p , h , m , e , 2 * v + 1);

	g[h][v] = __gcd(g[h][2 * v] , g[h][2 * v + 1]);
}

ll getGcd(int l , int r , int h , int s = 0 , int e = cmpx.size() , int v = 1)
{
	if(l <= s && e <= r)
		return g[h][v];
	if(r <= s || e <= l)
		return 0;

	int m = (s + e) / 2;
	return __gcd(getGcd(l , r , h , s , m , 2 * v) , getGcd(l , r , h , m , e , 2 * v + 1));
}

ll get(int l , int r , int l2 , int r2 , int s = 0 , int e = cmpx.size() , int h = 0)
{
	if(l <= s && e <= r)
	{
		y[maxn - 1] = l2; l2 = lower_bound(seg[h] + s , seg[h] + e , maxn - 1 , cmpy) - seg[h];
		y[maxn - 1] = r2; r2 = upper_bound(seg[h] + s , seg[h] + e , maxn - 1 , cmpy) - seg[h];
		return getGcd(l2 , r2 , h);
	}
	if(r <= s || e <= l)
		return 0;

	int m = (s + e) / 2;

	return __gcd(get(l , r , l2 , r2 , s , m , h + 1) , get(l , r , l2 , r2 , m , e , h + 1));
}

void rebuild()
{
	memset(where , -1 , sizeof where);
	cmpx.clear();
	for(int i = 0; i < sz; i++)
		cmpx.pb(x[i]);

	sort(cmpx.begin() , cmpx.end());

	map<int , int> mp;
	for(int i = 0; i < sz; i++)
	{
		int p = lower_bound(cmpx.begin() , cmpx.end() , x[i]) - cmpx.begin();
		p += mp[x[i]];
		mp[x[i]]++;

		tmp[p] = i;
	}

	build();
	for(int i = 0; i < maxb; i++)
		buildgcd(i);
}

void init(int R, int C)
{
	memset(where , -1 , sizeof where);
	R = R , C = C;
}

void update(int P, int Q, long long K)
{
	if(MP.count({P , Q}))
	{
		int ind = MP[make_pair(P , Q)];
		val[ind] = K;

		for(int i = 0; i < maxb; i++)
			if(where[i][ind] != -1)
				updategcd(where[i][ind] , i);
	}
	else
	{
		x[sz] = P , y[sz] = Q , val[sz] = K;
		MP[make_pair(P , Q)] = sz;
		sz++;
		if(sz % sq == 0)
			rebuild();
	}
}

long long calculate(int l1, int l2, int r1, int r2)
{
	ll res = 0;
	for(int i = 0; i < sz; i++)
		if(l1 <= x[i] && x[i] <= r1 && l2 <= y[i] && y[i] <= r2)
			res = __gcd(res , val[i]);

	int l = lower_bound(cmpx.begin() , cmpx.end() , l1) - cmpx.begin();
	int r = upper_bound(cmpx.begin() , cmpx.end() , r1) - cmpx.begin();

	return __gcd(res , get(l , r , l2 , r2));
}

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 888 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1148 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 2 ms 888 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 2 ms 888 KB Output is correct
10 Correct 2 ms 888 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 2 ms 888 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Execution timed out 13063 ms 6736 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 2 ms 888 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 2 ms 888 KB Output is correct
10 Correct 2 ms 888 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Execution timed out 13021 ms 6852 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 888 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 2 ms 888 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 2 ms 888 KB Output is correct
10 Correct 2 ms 888 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Execution timed out 13062 ms 6852 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 2 ms 888 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 2 ms 888 KB Output is correct
10 Correct 2 ms 888 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Execution timed out 13082 ms 6960 KB Time limit exceeded
13 Halted 0 ms 0 KB -