Submission #103932

#	Time	Username	Problem	Language	Result	Execution time	Memory
103932		dupreez	New Home (APIO18_new_home)	C++14	0 / 100	20 ms	14592 KiB

new_home

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <cstdio>
#include <cmath>
#include <bitset>
#define mk make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;

const ll MOD = 1000000007, N =300010, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }, MIN = -7230040172838, MAX = 7230040172838;
const int S = 60;
ll mn(ll a, ll b) {
	if (a == -1)return b;
	if (b == -1)return a;
	return min(a, b);
}
static ll gcd(ll v1, ll v2) {
	if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
}

ll pw(ll v1, ll v2) {
	ll v3 = 1;
	while (v2 > 0) {
		if (v2 % 2)v3 = (v3*v1) % MOD;
		v1 = (v1*v1) % MOD;
		v2 /= 2;
	}
	return v3;
}

int n, Q, as[N], k, id[N];
pos ql[N];
vector<int> ls[N];
priority_queue<pos> q,q2;
multiset<int> mnl, mxl;

int main() {
	cin >> n >> k >> Q;

	for (int i = 1; i <= n; i++) {
		int v1, v2, v3, v4;
		cin >> v1 >> v2 >> v3 >> v4;
		ls[v1].pb(v2);
	}

	for (int i = 1; i <= k; i++) {
		sort(ls[i].begin(), ls[i].end());
		if (ls[i].empty()) {
			for (int i = 0; i < Q; i++)cout << -1 << endl;
			return 0;
		}
		q.push(mk(-ls[i][0], i));
		mxl.insert(-ls[i][0]);
	}

	for (int i = 0; i < Q; i++) {
		ll v1, v2; cin >> v1 >> v2;
		ql[i] = mk(v2, i);
	}
	sort(ql, ql + Q);
	for (int qi = 0; qi < Q; qi++) {
		while (!q2.empty() && -q2.top().first <= ql[qi].first) {
			ll ci = -q2.top().first; q2.pop();
			if (id[ci] != 0) { mnl.erase(mnl.find(ls[ci][id[ci] - 1])); }
			mxl.insert(-ls[ci][id[ci]]);
		}

		while (!q.empty() && -q.top().first <= ql[qi].first) {
			ll lv = -q.top().first, ci = q.top().second;
			q.pop();
			id[ci]++;
			if(id[ci]<ls[ci].size())
				q.push(mk(-ls[ci][id[ci]], ci));
			mxl.erase(mxl.find(-lv));
			mnl.insert(lv);
			ll nv;
			if (id[ci] < ls[ci].size())nv = (ls[ci][id[ci]] + lv) / 2;
			else nv = MAX;
			q2.push(mk(-nv, ci));
		}

		while (!q2.empty() && -q2.top().first <= ql[qi].first) {
			int ci = -q2.top().first; q2.pop();
			if (id[ci] != 0) { mnl.erase(mnl.find(ls[ci][id[ci] - 1])); }
			mxl.insert(-ls[ci][id[ci]]);
		}

		ll v1 = abs(*mxl.begin()), v2 = abs(*mnl.begin()),v3=ql[qi].first;
		as[ql[qi].second] = max(abs(v1 - v3), abs(v2 - v3));

	}

	for (int i = 0; i < Q; i++)cout << as[i] << endl;

	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'll gcd(ll, ll)':
new_home.cpp:27:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
  ^~
new_home.cpp:27:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
                         ^~
new_home.cpp: In function 'int main()':
new_home.cpp:81:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(id[ci]<ls[ci].size())
       ~~~~~~^~~~~~~~~~~~~~
new_home.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (id[ci] < ls[ci].size())nv = (ls[ci][id[ci]] + lv) / 2;
        ~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20