#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define maxN 1000000000
#define N 300006
using namespace std;
struct Store {
int x, type, a, b;
};
struct Query {
int x, t, id;
bool operator < (const Query &rhs) const {
return t < rhs.t;
}
};
struct Segment {
int L, R, a, b;
Segment(int _L=0, int _R=0, int _a=0, int _b=0) : L(_L), R(_R), a(_a), b(_b) {}
};
bool cmpSegLR(Segment p, Segment q) {
return p.L < q.L || (p.L == q.L && p.R < q.R);
}
bool cmpSegRL(Segment p, Segment q) {
return p.R > q.R || (p.R == q.R && p.L > q.L);
}
struct SegOnYear {
vector<int> t[(3*N) << 2];
void update(int l, int r, int id, int x, int y, int val) {
if (l > y || r < x) return;
if (l >= x && r <= y) {
t[id].PB(val);
return;
}
int mid = (r + l)/2;
update(l, mid, id*2, x, y, val);
update(mid+1, r, id*2+1, x, y, val);
}
}tSegLR, tSegRL;
Store sto[N];
Query que[N];
map<pii, int> maLR, maRL;
vector<Segment> segLR, segRL;
int n, k, Q, tMax;
set<int> curSet;
vector<pair<int, pii> > allType[N];
int res[N];
int findLef(int x) {
auto it = curSet.upper_bound(x); it--;
return (*it);
}
int findRig(int x) {
auto it = curSet.upper_bound(x);
return (*it);
}
void addSeg(int L, int R, int time) {
int mid = (R + L)/2;
maLR[mp(L, mid)] = time;
maRL[mp(mid, R)] = time;
}
void remSeg(int L, int R, int time) {
int mid = (R + L)/2;
if (L != -2*maxN)
segLR.PB(Segment(L, mid, maLR[mp(L, mid)], max(maLR[mp(L, mid)], time)));
if (R != 2*maxN)
segRL.PB(Segment(mid, R, maRL[mp(mid, R)], max(maRL[mp(mid, R)], time)));
}
void setup() {
cin >> n >> k >> Q;
vector<int> allYear;
FOR(i, 1, n) {
cin >> sto[i].x >> sto[i].type >> sto[i].a >> sto[i].b;
sto[i].x *= 2;
allYear.PB(sto[i].a); allYear.PB(sto[i].b);
}
FOR(i, 1, Q) {
cin >> que[i].x >> que[i].t, que[i].x *= 2;
que[i].id = i;
allYear.PB(que[i].t);
}
sort(allYear.begin(), allYear.end());
allYear.resize(unique(allYear.begin(), allYear.end()) - allYear.begin());
FOR(i, 1, n) {
sto[i].a = lower_bound(allYear.begin(), allYear.end(), sto[i].a) - allYear.begin() + 1;
sto[i].b = lower_bound(allYear.begin(), allYear.end(), sto[i].b) - allYear.begin() + 1;
}
FOR(i, 1, Q) {
que[i].t = lower_bound(allYear.begin(), allYear.end(), que[i].t) - allYear.begin() + 1;
}
tMax = allYear.size();
sort(que+1, que+Q+1);
FOR(i, 1, n) {
int type = sto[i].type;
allType[type].PB(mp(sto[i].a, mp(0, sto[i].x)));
allType[type].PB(mp(sto[i].b, mp(1, sto[i].x)));
}
FOR(i, 1, k) {
curSet.clear();
curSet.insert(-2*maxN); curSet.insert(2*maxN);
addSeg(-2*maxN, 2*maxN, tMax+1);
sort(allType[i].begin(), allType[i].end());
for (auto z : allType[i]) {
int x = z.S.S;
int time = z.F;
int type = z.S.F;
if (type == 0) {
int L = findLef(x), R = findRig(x);
remSeg(L, R, time);
addSeg(L, x, time);
addSeg(x, R, time);
curSet.insert(x);
}
else {
curSet.erase(x);
int L = findLef(x), R = findRig(x);
remSeg(L, x, time);
remSeg(x, R, time);
addSeg(L, R, time);
}
}
}
sort(segLR.begin(), segLR.end(), cmpSegLR);
sort(segRL.begin(), segRL.end(), cmpSegRL);
for (int i = 0; i < segLR.size(); i++) {
int a = segLR[i].a;
int b = segLR[i].b;
tSegLR.update(1, tMax, 1, a, b, i);
}
for (int i = 0; i < segRL.size(); i++) {
int a = segRL[i].a;
int b = segRL[i].b;
tSegRL.update(1, tMax, 1, a, b, i);
}
}
void rayLR(vector<int> seg, vector<int> idQ) {
if (seg.size() == 0) return;
int pp = -1;
for (auto id : idQ) {
int x = que[id].x;
while (pp < (int)seg.size() - 1 && segLR[seg[pp+1]].L <= x)
pp++;
int idAns = que[id].id;
if (pp >= 0)
res[idAns] = max(res[idAns], x-segLR[seg[pp]].L);
}
}
void rayRL(vector<int> seg, vector<int> idQ) {
if (seg.size() == 0) return;
reverse(idQ.begin(), idQ.end());
int pp = -1;
for (auto id : idQ) {
int x = que[id].x;
while (pp < (int) seg.size() - 1 && segRL[seg[pp+1]].R >= x)
pp++;
int idAns = que[id].id;
if (pp >= 0)
res[idAns] = max(res[idAns], segRL[seg[pp]].R-x);
}
}
void solve(int l, int r, int id, vector<int> curQ) {
if (curQ.size() == 0) return;
rayLR(tSegLR.t[id], curQ);
rayRL(tSegRL.t[id], curQ);
if (l == r) return;
int mid = (r + l)/2;
vector<int> qLef, qRig;
for (auto id : curQ) {
if (que[id].t <= mid) qLef.PB(id);
else qRig.PB(id);
}
solve(l, mid, id*2, qLef);
solve(mid+1, r, id*2+1, qRig);
}
int cnt[N], impossible[N];
void checkImpossible() {
vector<pair<pii, int> > check;
FOR(i, 1, n) {
check.PB(mp(mp(sto[i].a, 0), sto[i].type));
check.PB(mp(mp(sto[i].b, 2), sto[i].type));
}
FOR(i, 1, Q) {
check.PB(mp(mp(que[i].t, 1), que[i].id));
}
sort(check.begin(), check.end());
int curCnt = 0;
for (auto z : check) {
int time = z.F.F;
int type = z.F.S;
int kind = z.S;
if (type == 1) impossible[kind] = (curCnt < k);
else {
if (cnt[kind]) curCnt--;
if (type == 0) cnt[kind]++;
else cnt[kind]--;
if (cnt[kind]) curCnt++;
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("INP.TXT", "r", stdin);
setup();
vector<int> allQ;
FOR(i, 1, Q) allQ.PB(i);
solve(1, tMax, 1, allQ);
checkImpossible();
FOR(i, 1, Q) {
if (impossible[i]) cout <<-1<<'\n';
else cout <<res[i]/2<<'\n';
}
}
Compilation message
new_home.cpp: In function 'void setup()':
new_home.cpp:136:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < segLR.size(); i++) {
~~^~~~~~~~~~~~~~
new_home.cpp:141:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < segRL.size(); i++) {
~~^~~~~~~~~~~~~~
new_home.cpp: In function 'void checkImpossible()':
new_home.cpp:210:13: warning: unused variable 'time' [-Wunused-variable]
int time = z.F.F;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
176624 KB |
Output is correct |
| 2 |
Correct |
204 ms |
176504 KB |
Output is correct |
| 3 |
Correct |
196 ms |
176556 KB |
Output is correct |
| 4 |
Incorrect |
168 ms |
176504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
176624 KB |
Output is correct |
| 2 |
Correct |
204 ms |
176504 KB |
Output is correct |
| 3 |
Correct |
196 ms |
176556 KB |
Output is correct |
| 4 |
Incorrect |
168 ms |
176504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4999 ms |
359056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5100 ms |
405932 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
176624 KB |
Output is correct |
| 2 |
Correct |
204 ms |
176504 KB |
Output is correct |
| 3 |
Correct |
196 ms |
176556 KB |
Output is correct |
| 4 |
Incorrect |
168 ms |
176504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
176624 KB |
Output is correct |
| 2 |
Correct |
204 ms |
176504 KB |
Output is correct |
| 3 |
Correct |
196 ms |
176556 KB |
Output is correct |
| 4 |
Incorrect |
168 ms |
176504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
