oj.uz

답안 #128328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128328 2019-07-10T17:30:58 Z qkxwsm 새 집 (APIO18_new_home) C++14
10 / 100
 4196 ms 248352 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define LIM 100000007
#define INF 1000000007
#define LLINF 2696969696969696969ll
#define MAXN 600013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pii, pii> ppp;
typedef pair<pii, int> ppi;

int N, K, Q, P;
vector<ppp> arr;
vector<ppi> quer;
int ans[MAXN];
vpi arrs[MAXN << 1], quers[MAXN << 1];
vi compress, pos;
vpi func;
int mx, iter;

void ins(int w, int L, int R, int a, int b, pii p)
{
	if (a <= L && R <= b)
	{
		arrs[w].PB(p);
		return;
	}
	int mid = (L + R) >> 1;
	if (a <= mid) ins(w << 1, L, mid, a, b, p);
	if (mid < b) ins(w << 1 | 1, mid + 1, R, a, b, p);
}
void qins(int w, int L, int R, int a, pii p)
{
	quers[w].PB(p);
	if (L == R) return;
	int mid = (L + R) >> 1;
	if (a <= mid) qins(w << 1, L, mid, a, p);
	else qins(w << 1 | 1, mid + 1, R, a, p);
}
void proc(int w, int L, int R)
{
	if (L != R)
	{
		int mid = (L + R) >> 1;
		proc(w << 1, L, mid);
		proc(w << 1 | 1, mid + 1, R);
	}
	if (quers[w].empty()) return;
	int freq = 0;
	FOR(i, 0, SZ(arrs[w]))
	{
		if (i == SZ(arrs[w]) - 1 || arrs[w][i].fi != arrs[w][i + 1].fi) freq++;
	}
	if (freq != K) return;
	vi curans(SZ(quers[w]));
	freq = 0; func.clear();
	FOR(i, 0, SZ(arrs[w]))
	{
		pos.PB(arrs[w][i].se);
		if (i == SZ(arrs[w]) - 1 || arrs[w][i].fi != arrs[w][i + 1].fi)
		{
			func.PB({0, pos[0]});
			FOR(j, 1, SZ(pos))
			{
				func.PB({(pos[j - 1] + pos[j] + 1) >> 1, pos[j]});
			}
			pos.clear();
		}
	}
	sort(ALL(func));
	mx = -INF; iter = 0;
	FOR(i, 0, SZ(func))
	{
		while(iter < SZ(quers[w]) && quers[w][iter].fi < func[i].fi)
		{
			ckmax(curans[iter], -quers[w][iter].fi + mx);
			iter++;
		}
		ckmax(mx, func[i].se);
	}
	while(iter < SZ(quers[w]))
	{
		ckmax(curans[iter], -quers[w][iter].fi + mx);
		iter++;
	}
	freq = 0; func.clear();
	FOR(i, 0, SZ(arrs[w]))
	{
		pos.PB(arrs[w][i].se);
		if (i == SZ(arrs[w]) - 1 || arrs[w][i].fi != arrs[w][i + 1].fi)
		{
			func.PB({LIM, -pos.back()});
			FORD(j, SZ(pos) - 1, 0)
			{
				func.PB({(pos[j] + pos[j + 1]) >> 1, -pos[j]});
			}
			pos.clear();
		}
	}
	sort(ALL(func));
	mx = -INF; iter = SZ(quers[w]) - 1;
	FORD(i, SZ(func), 0)
	{
		while(iter >= 0 && quers[w][iter].fi > func[i].fi)
		{
			ckmax(curans[iter], quers[w][iter].fi + mx);
			iter--;
		}
		ckmax(mx, func[i].se);
	}
	while(iter >= 0)
	{
		ckmax(curans[iter], quers[w][iter].fi + mx);
		iter--;
	}
	FOR(i, 0, SZ(quers[w]))
	{
		ckmin(ans[quers[w][i].se], curans[i]);
	}
	return;
}

int32_t main()
{
	if (fopen("file.in", "r"))
	{
		freopen("file.in", "r", stdin);
	}
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K >> Q;
	arr.resize(N); quer.resize(Q);
	FOR(i, 0, N)
	{
		cin >> arr[i].fi.se >> arr[i].fi.fi >> arr[i].se.fi >> arr[i].se.se;
		arr[i].fi.fi--;
	}
	FOR(i, 0, Q)
	{
		cin >> quer[i].fi.fi >> quer[i].fi.se; //location, time
		compress.PB(quer[i].fi.se);
		quer[i].se = i;
	}
	compress.PB(0); compress.PB(LIM);
	sort(ALL(compress));
	compress.erase(unique(ALL(compress)), compress.end());
	FOR(i, 0, N)
	{
		arr[i].se.fi = LB(ALL(compress), arr[i].se.fi) - compress.begin();
		arr[i].se.se = UB(ALL(compress), arr[i].se.se) - compress.begin() - 1;
	}
	FOR(i, 0, Q)
	{
		quer[i].fi.se = LB(ALL(compress), quer[i].fi.se) - compress.begin();
		ans[i] = INF;
	}
	sort(ALL(quer));
	//type, location, times (whaever)
	//ok this is type what:
	sort(ALL(arr));
	FOR(i, 0, SZ(arr))
	{
		int t1 = arr[i].se.fi, t2 = arr[i].se.se;
		if (t1 > t2) continue;
		ins(1, 0, SZ(compress) - 1, t1, t2, arr[i].fi);
	}
	FOR(i, 0, SZ(quer))
	{
		qins(1, 0, SZ(compress) - 1, quer[i].fi.se, {quer[i].fi.fi, quer[i].se}); //location, id
	}
	proc(1, 0, SZ(compress) - 1);
	FOR(i, 0, Q)
	{
		if (ans[i] >= LIM)
		{
			cout << "-1\n";
			continue;
		}
		// cerr << "ans " << ans[i] << endl;
		cout << ans[i] << '\n';
	}
	return 0;
}

Compilation message

new_home.cpp: In function 'int32_t main()':
new_home.cpp:157:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("file.in", "r", stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 56696 KB Output is correct
2 Correct 57 ms 56696 KB Output is correct
3 Correct 57 ms 56696 KB Output is correct
4 Incorrect 56 ms 56696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 56696 KB Output is correct
2 Correct 57 ms 56696 KB Output is correct
3 Correct 57 ms 56696 KB Output is correct
4 Incorrect 56 ms 56696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4049 ms 245936 KB Output is correct
2 Correct 3050 ms 247668 KB Output is correct
3 Correct 4172 ms 245936 KB Output is correct
4 Correct 4094 ms 245916 KB Output is correct
5 Correct 2247 ms 248352 KB Output is correct
6 Correct 2976 ms 248116 KB Output is correct
7 Correct 4196 ms 246136 KB Output is correct
8 Correct 4097 ms 246128 KB Output is correct
9 Correct 3973 ms 245976 KB Output is correct
10 Correct 3411 ms 245956 KB Output is correct
11 Correct 2637 ms 241088 KB Output is correct
12 Correct 2968 ms 242084 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2945 ms 224784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 56696 KB Output is correct
2 Correct 57 ms 56696 KB Output is correct
3 Correct 57 ms 56696 KB Output is correct
4 Incorrect 56 ms 56696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 56696 KB Output is correct
2 Correct 57 ms 56696 KB Output is correct
3 Correct 57 ms 56696 KB Output is correct
4 Incorrect 56 ms 56696 KB Output isn't correct
5 Halted 0 ms 0 KB -