Submission #559321

#	Time	Username	Problem	Language	Result	Execution time	Memory
559321		Zanite	New Home (APIO18_new_home)	C++17	0 / 100	698 ms	128020 KiB

new_home

// "I assure you that you guys won't make it to the top 4"
// - Tzaph, 21 December 2021

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ll long long
#define ld long double
#define si short int
#define i8 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define psi pair<si, si>
#define pi8 pair<i8, i8>
#define pq priority_queue
#define fi first
#define se second

#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'

#define yume using
#define wo namespace
#define kanaeyo std

yume wo kanaeyo;

template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}

const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;

const ld EPS = 1e-9;
const ld iEPS = 1e-6;

const int maxN = 3e5 + 5;

struct Store {
	ll loc, typ, a, b;
	Store(ll _loc, ll _typ, ll _a, ll _b) :
		loc(_loc),
		typ(_typ),
		a(_a),
		b(_b)
	{}
};

struct Process {
	ll proctype; // 0 = store opening, 1 = query, 2 = store closing
	ll loc, typ, a, b, idx;
	Process(ll _proctype, ll _loc, ll _typ, ll _a, ll _b, ll _idx) :
		proctype(_proctype),
		loc(_loc),
		typ(_typ),
		a(_a),
		b(_b),
		idx(_idx)
	{}

	bool operator < (const Process &other) const {
		return (a < other.a) || (a == other.a && proctype < other.proctype);
	}
};

struct Segtree {
	vector<pll> seg; // {min, max}
	pll DEFAULT = {INF, -INF};

	Segtree(ll _sz) {
		seg.assign((_sz << 2) + 1, DEFAULT);
	}

	pll merge(pll A, pll B) {
		return {min(A.fi, B.fi), max(A.se, B.se)};
	}

	void update(ll pos, ll l, ll r, ll idx, ll val) {
		if (l == r) {
			seg[pos] = {val, val};
			return;
		}

		ll m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
		if (idx <= m) {
			update(lc, l, m, idx, val);
		} else {
			update(rc, m+1, r, idx, val);
		}
		seg[pos] = merge(seg[lc], seg[rc]);
	}

	pll query(ll pos, ll l, ll r, ll ql, ll qr) {
		if (l > qr || ql > r) {return DEFAULT;}
		if (ql <= l && r <= qr) {return seg[pos];}

		ll m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
		return merge(
			query(lc, l, m, ql, qr),
			query(rc, m+1, r, ql, qr)
		);
	}
};

ll n, k, q, SZ;
vector<Store> stores;
vector<pair<pll, ll>> queries;
vector<ll> compress, answers;
vector<Process> processes;
vector<ll> openStores;
ll openStoreCount;

int main() {
	scanf("%lld %lld %lld", &n, &k, &q);
	for (ll x, t, a, b, i = 1; i <= n; i++) {
		scanf("%lld %lld %lld %lld", &x, &t, &a, &b);
		stores.push_back(Store(x, t, a, b));
		compress.push_back(a);
		compress.push_back(b);
	}
	for (ll l, y, i = 0; i < q; i++) {
		scanf("%lld %lld", &l, &y);
		queries.push_back({{l, y}, i});
		compress.push_back(y);
	}
	answers.assign(q, 0);
	openStores.assign(k+1, 0);

	// coordinate compression
	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(), compress.end()), compress.end());
	for (auto &s : stores) {
		s.a = lower_bound(compress.begin(), compress.end(), s.a) - compress.begin() + 1;
		s.b = lower_bound(compress.begin(), compress.end(), s.b) - compress.begin() + 1;
	}
	for (auto &q : queries) {
		q.fi.se = lower_bound(compress.begin(), compress.end(), q.fi.se) - compress.begin() + 1;
	}
	SZ = compress.size();
	Segtree S = Segtree(SZ);

	// sweep on the opening and closing time of the store
	// to see if all k types of stores are open at the time of query
	for (auto s : stores) {
		processes.push_back(Process(0, s.loc, s.typ, s.a, s.b, -1));
		processes.push_back(Process(2, -1, s.typ, s.b, -1, -1));
	}
	for (auto q : queries) {
		processes.push_back(Process(1, q.fi.fi, -1, q.fi.se, -1, q.se));
	}
	sort(processes.begin(), processes.end());

	for (auto p : processes) {
		if (p.proctype == 0) {
			// Store opens
			if (openStores[p.typ] == 0) {openStoreCount++;}
			openStores[p.typ]++;

			// Update segtree
			S.update(1, 1, SZ, p.b, p.loc);

		} else if (p.proctype == 1) {
			// Answer query
			// If not all K types of stores are open, answer -1
			if (openStoreCount != k) {
				answers[p.idx] = -1;
			} else {
				// Else, query segtree
				pll ext = S.query(1, 1, SZ, p.a, SZ);
				answers[p.idx] = max(p.loc - ext.fi, ext.se - p.loc);
			}

		} else if (p.proctype == 2) {
			// Store closes
			openStores[p.typ]--;
			if (openStores[p.typ] == 0) {openStoreCount--;}
		}
	}

	for (auto a : answers) {
		printf("%lld\n", a);
	}
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%lld %lld %lld", &n, &k, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%lld %lld %lld %lld", &x, &t, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |   scanf("%lld %lld", &l, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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