#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
template<typename T>
void read(T &x){
char ch;
for(ch = getchar(); !isdigit(ch); ch = getchar());
x = ch - '0';
for(ch = getchar(); isdigit(ch); ch = getchar())
x = x * 10 + ch - '0';
}
template<typename T>
void write(T x){
if (x < 0){
putchar('-');
write(-x);
return;
}
if (x < 10){
putchar(x + '0');
} else {
write(x / 10);
putchar(x % 10 + '0');
}
}
const int N = 3e5 + 10;
const int INF = 4e8 + 10;
struct segment{
int type, x, y, a, b;
segment(int _type = 0, int _x = 0, int _y = 0, int _a = 0, int _b = 0){
type = _type;
x = _x;
y = _y;
a = _a;
b = _b;
}
bool operator < (const segment &other){
if (type != other.type)
return type < other.type;
if (x != other.x)
return x < other.x;
return y < other.y;
}
};
struct query{
int x, t, id;
bool operator < (const query &other){
return x < other.x;
}
};
struct node{
int x, id, idL, idR;
node(int _x = 0, int _id = 0, int _idL = 0, int _idR = 0){
x = _x;
id = _id;
idL = _idL;
idR = _idR;
}
};
bool operator < (const node &a, const node &b){
if (a.x != b.x)
return a.x < b.x;
if (a.id != b.id)
return a.id < b.id;
if (a.idL != b.idL)
return a.idL < b.idL;
return a.idR < b.idR;
}
struct event{
int t, type, id;
event(int _t = 0, int _type = 0, int _id = 0){
t = _t;
type = _type;
id = _id;
}
bool operator < (const event &other){
if (t != other.t)
return t < other.t;
if (type != other.type)
return type < other.type;
return id < other.id;
}
};
int n, k, nQ;
int x[N], t[N], a[N], b[N], ans[N];
query q[N];
int nSeg, nE;
segment seg[10 * N];
event e[N * 2];
int nTQ, tQ[N];
void readInput(){
read(n);
read(k);
read(nQ);
for(int i = 1; i <= n; i++){
read(x[i]);
read(t[i]);
read(a[i]);
read(b[i]);
}
for(int i = 1; i <= nQ; i++){
read(q[i].x);
read(q[i].t);
q[i].id = i;
}
}
void updateSeg(node &l, node &r, int a){
int mid = (l.x + r.x) >> 1;
seg[++nSeg] = segment(1, mid, mid - l.x, a, -1);
if (l.idR != -1)
seg[l.idR].b = a - 1;
l.idR = nSeg;
seg[++nSeg] = segment(-1, mid, r.x - mid, a, -1);
if (r.idL != -1)
seg[r.idL].b = a - 1;
r.idL = nSeg;
}
vector <int> type[N];
void init(){
for(int i = 1; i <= n; i++)
x[i] <<= 1;
for(int i = 1; i <= nQ; i++)
q[i].x <<= 1;
for(int i = 1; i <= n; i++)
type[t[i]].push_back(i);
for(int typ = 1; typ <= k; typ++){
nE = 0;
for(int pos : type[typ]){
e[++nE] = event(a[pos], 1, pos);
e[++nE] = event(b[pos] + 1, -1, pos);
}
sort(e + 1, e + 1 + nE);
set <node> S;
node l(-INF, -1, -1, -1), r(INF, -1, -1, -1);
updateSeg(l, r, 0);
S.insert(l);
S.insert(r);
for(int i = 1; i <= nE; i++){
if (e[i].type == -1){
auto it = S.lower_bound(node(x[e[i].id], e[i].id, -1, -1));
auto itL = S.end(), itR = S.end();
if (it != S.end()){
itR = it;
++itR;
}
if (it != S.begin()){
itL = it;
--itL;
}
node d = *it;
if (d.idL != -1)
seg[d.idL].b = e[i].t - 1;
if (d.idR != -1)
seg[d.idR].b = e[i].t - 1;
S.erase(it);
if (itL != S.end() && itR != S.end()){
node nL = *itL, nR = *itR;
S.erase(itL);
S.erase(itR);
updateSeg(nL, nR, e[i].t);
S.insert(nL);
S.insert(nR);
}
} else {
auto it = S.lower_bound(node(x[e[i].id], e[i].id, -1, -1));
auto itR = it, itL = S.end();
if (itR != S.begin()){
itL = itR;
--itL;
}
node d = node(x[e[i].id], e[i].id, -1, -1);
if (itL != S.end()){
node nL = *itL;
S.erase(itL);
updateSeg(nL, d, e[i].t);
S.insert(nL);
}
if (itR != S.end()){
node nR = *itR;
S.erase(itR);
updateSeg(d, nR, e[i].t);
S.insert(nR);
}
S.insert(d);
}
}
node nL = *S.begin(), nR = *(++S.begin());
seg[nL.idR].b = INF;
seg[nR.idL].b = INF;
}
}
struct segmentTree{
vector <int> d[N * 4];
int cnt[N * 4], cur[N * 4];
void fakeAddSeg(int id, int l, int r, int u, int v){
if (v < l || r < u)
return;
if (u <= l && r <= v){
cnt[id]++;
return;
}
int mid = (l + r) >> 1;
fakeAddSeg(id << 1, l, mid, u, v);
fakeAddSeg(id << 1 | 1, mid + 1, r, u, v);
}
void normalize(int id, int l, int r){
d[id].resize(cnt[id]);
if (l == r)
return;
int mid = (l + r) >> 1;
normalize(id << 1, l, mid);
normalize(id << 1 | 1, mid + 1, r);
}
void addSeg(int id, int l, int r, int u, int v, int pos){
if (v < l || r < u)
return;
if (u <= l && r <= v){
d[id][cur[id]++] = pos;
return;
}
int mid = (l + r) >> 1;
addSeg(id << 1, l, mid, u, v, pos);
addSeg(id << 1 | 1, mid + 1, r, u, v, pos);
}
void solve(int id, int l, int r, vector<query> &curQ){
if (curQ.empty())
return;
auto ptr1 = d[id].begin();
int maxVal = -INF;
for(auto ptrQ = curQ.begin(); ptrQ != curQ.end(); ++ptrQ){
while (ptr1 != d[id].end() && seg[*ptr1].type == -1 && seg[*ptr1].x <= ptrQ -> x){
maxVal = max(maxVal, seg[*ptr1].x + seg[*ptr1].y);
++ptr1;
}
ans[ptrQ -> id] = max(ans[ptrQ -> id], maxVal - ptrQ -> x);
}
auto ptr2 = d[id].rbegin();
maxVal = -INF;
for(auto ptrQ = curQ.rbegin(); ptrQ != curQ.rend(); ++ptrQ){
while (ptr2 != d[id].rend() && seg[*ptr2].type == 1 && seg[*ptr2].x >= ptrQ -> x){
maxVal = max(maxVal, seg[*ptr2].y - seg[*ptr2].x);
++ptr2;
}
ans[ptrQ -> id] = max(ans[ptrQ -> id], maxVal + ptrQ -> x);
}
if (l == r)
return;
int mid = (l + r) >> 1;
vector <query> lQ, rQ;
for(query q : curQ)
if (q.t <= mid)
lQ.push_back(q);
else
rQ.push_back(q);
solve(id << 1, l, mid, lQ);
solve(id << 1 | 1, mid + 1, r, rQ);
}
} ST;
void solve(){
sort(seg + 1, seg + 1 + nSeg);
sort(q + 1, q + 1 + nQ);
nTQ = 0;
for(int i = 1; i <= nQ; i++)
tQ[++nTQ] = q[i].t;
sort(tQ + 1, tQ + 1 + nTQ);
nTQ = unique(tQ + 1, tQ + 1 + nTQ) - (tQ + 1);
for(int i = 1; i <= nQ; i++)
q[i].t = lower_bound(tQ + 1, tQ + 1 + nTQ, q[i].t) - tQ;
for(int i = 1; i <= nSeg; i++){
seg[i].a = lower_bound(tQ + 1, tQ + 1 + nTQ, seg[i].a) - tQ;
seg[i].b = upper_bound(tQ + 1, tQ + 1 + nTQ, seg[i].b) - tQ - 1;
if (seg[i].a <= seg[i].b)
ST.fakeAddSeg(1, 1, nTQ, seg[i].a, seg[i].b);
}
ST.normalize(1, 1, nTQ);
for(int i = 1; i <= nSeg; i++)
if (seg[i].a <= seg[i].b)
ST.addSeg(1, 1, nTQ, seg[i].a, seg[i].b, i);
vector <query> curQ;
for(int i = 1; i <= nQ; i++)
curQ.push_back(q[i]);
ST.solve(1, 1, nTQ, curQ);
for(int i = 1; i <= nQ; i++){
write(ans[i] >= (INF >> 1)? -1 : (ans[i] >> 1));
putchar('\n');
}
}
int main(){
freopen("inp.txt", "r", stdin);
freopen("out.txt", "w", stdout);
readInput();
init();
solve();
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:327:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
327 | freopen("inp.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:328:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
328 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5060 ms |
101168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5060 ms |
101168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5105 ms |
101256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5067 ms |
101184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5060 ms |
101168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5060 ms |
101168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
