oj.uz

답안 #123795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123795 2019-07-02T07:00:54 Z Mahdi_Jfri 게임 (IOI13_game) C++14
80 / 100
 4448 ms 20608 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 = sz / sq * sq; 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1020 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 3 ms 892 KB Output is correct
9 Correct 3 ms 892 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
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 892 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2463 ms 11568 KB Output is correct
5 Correct 1418 ms 14576 KB Output is correct
6 Correct 2849 ms 12064 KB Output is correct
7 Correct 3226 ms 11816 KB Output is correct
8 Correct 1328 ms 9676 KB Output is correct
9 Correct 3008 ms 11996 KB Output is correct
10 Correct 4159 ms 11488 KB Output is correct
11 Correct 3 ms 888 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 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 2 ms 860 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 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 3 ms 888 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 2477 ms 11868 KB Output is correct
13 Correct 2859 ms 8736 KB Output is correct
14 Correct 744 ms 6648 KB Output is correct
15 Correct 2839 ms 9424 KB Output is correct
16 Correct 2356 ms 11528 KB Output is correct
17 Correct 1735 ms 10052 KB Output is correct
18 Correct 3605 ms 12792 KB Output is correct
19 Correct 3146 ms 13144 KB Output is correct
20 Correct 4232 ms 12556 KB Output is correct
21 Correct 3 ms 888 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 2 ms 892 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 Correct 2446 ms 11488 KB Output is correct
13 Correct 1421 ms 14508 KB Output is correct
14 Correct 2796 ms 12012 KB Output is correct
15 Correct 3221 ms 11808 KB Output is correct
16 Correct 1320 ms 9544 KB Output is correct
17 Correct 3052 ms 11812 KB Output is correct
18 Correct 4140 ms 11472 KB Output is correct
19 Correct 2478 ms 14552 KB Output is correct
20 Correct 2935 ms 8660 KB Output is correct
21 Correct 730 ms 6516 KB Output is correct
22 Correct 2854 ms 9420 KB Output is correct
23 Correct 2361 ms 11344 KB Output is correct
24 Correct 1731 ms 10076 KB Output is correct
25 Correct 3654 ms 12720 KB Output is correct
26 Correct 3181 ms 12888 KB Output is correct
27 Correct 4227 ms 12336 KB Output is correct
28 Correct 1638 ms 17796 KB Output is correct
29 Correct 2800 ms 20600 KB Output is correct
30 Correct 2932 ms 14076 KB Output is correct
31 Correct 2521 ms 11928 KB Output is correct
32 Correct 786 ms 10872 KB Output is correct
33 Correct 1156 ms 11072 KB Output is correct
34 Correct 2475 ms 14364 KB Output is correct
35 Correct 1875 ms 14980 KB Output is correct
36 Correct 3645 ms 18528 KB Output is correct
37 Correct 3363 ms 18772 KB Output is correct
38 Correct 4448 ms 18184 KB Output is correct
39 Correct 2584 ms 16016 KB Output is correct
40 Correct 2 ms 888 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 3 ms 892 KB Output is correct
10 Correct 2 ms 892 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 2461 ms 11712 KB Output is correct
13 Correct 1447 ms 14712 KB Output is correct
14 Correct 2766 ms 12216 KB Output is correct
15 Correct 3218 ms 11952 KB Output is correct
16 Correct 1323 ms 9592 KB Output is correct
17 Correct 3044 ms 12144 KB Output is correct
18 Correct 4134 ms 11588 KB Output is correct
19 Correct 2473 ms 14548 KB Output is correct
20 Correct 2865 ms 8732 KB Output is correct
21 Correct 728 ms 6520 KB Output is correct
22 Correct 2835 ms 9492 KB Output is correct
23 Correct 2375 ms 11236 KB Output is correct
24 Correct 1731 ms 9908 KB Output is correct
25 Correct 3575 ms 12752 KB Output is correct
26 Correct 3206 ms 12888 KB Output is correct
27 Correct 4241 ms 12408 KB Output is correct
28 Correct 1601 ms 17784 KB Output is correct
29 Correct 2796 ms 20608 KB Output is correct
30 Correct 2941 ms 14176 KB Output is correct
31 Correct 2497 ms 11872 KB Output is correct
32 Correct 790 ms 11032 KB Output is correct
33 Correct 1141 ms 11076 KB Output is correct
34 Correct 2459 ms 14160 KB Output is correct
35 Correct 1828 ms 15100 KB Output is correct
36 Correct 3641 ms 18528 KB Output is correct
37 Correct 3330 ms 18632 KB Output is correct
38 Correct 4413 ms 17972 KB Output is correct
39 Runtime error 1063 ms 18808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -