// "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
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
570 ms |
109288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
698 ms |
128020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
