#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define PR0(A, n) cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define FILE_NAME "new-home"
#define y1 __y1
#define y2 __y2
const int blockSize = 900;
const int MAX_N = 300002;
const int INF = 1e9;
struct rect {
int x1, x2, y1, y2, val;
rect() {}
rect(int _x1, int _x2, int _y1, int _y2, int _val) {
x1 = min(_x1, _x2); x2 = max(_x1, _x2);
y1 = min(_y1, _y2), y2 = max(_y1, _y2);
val = _val;
}
};
struct query {
int x, y, id;
query() {}
query(int x, int y, int id):
x(x), y(y), id(id) {}
bool operator<(const query & p) {
return x<p.x;
}
};
struct store {
int x, a, b;
store() {}
store(int x, int a, int b):
x(x), a(a), b(b) {}
bool operator<(const store &p) {
return x<p.x;
}
};
int n, nType, nQuery, nVal, nBlock=1, xMin[500], xMax[500], ps[MAX_N*3];
int res[MAX_N], res1[MAX_N], res2[MAX_N];
query q[MAX_N];
vector<store> storeType[MAX_N];
vector<query> block[500];
vector<rect> rectLeft, rectRight;
vector<pair<int, int> > tmp;
map<int, int> compVal;
struct node {
int a, b, x;
node() {}
node(int a, int b, int x):
a(a), b(b), x(x) {}
bool operator<(const node &p) const {
return b<p.b;
}
bool operator>(const node &p) const {
return b>p.b;
}
};
struct rmq_node {
pair<node, node> tr[MAX_N*4];
int sizeOfTree;
void init(int _size) {
sizeOfTree = _size;
for (int i=0; i<=4*_size; ++i)
tr[i].first = tr[i].second = node(-1, -1, -1);
}
void upd(int pos, node val, int l, int r, int id) {
if (pos<l || pos>r)
return;
if (l==pos && pos==r) {
tr[id].first = tr[id].second = val;
return;
}
int mid = (l + r) / 2;
upd(pos, val, l, mid, id*2);
upd(pos, val, mid+1, r, id*2+1);
if (tr[id*2].first.x==-1)
tr[id] = tr[id*2+1];
else if (tr[id*2+1].first.x==-1)
tr[id] = tr[id*2];
else {
tr[id].first = max(tr[id*2].first, tr[id*2+1].first);
tr[id].second = min(tr[id*2].second, tr[id*2+1].second);
}
}
node getMax(int u, int v, int l, int r, int id) {
if (v<l || u>r)
return node(-1, -1, -1);
if (u<=l && r<=v)
return tr[id].first;
int mid = (l + r) / 2;
node L = getMax(u, v, l, mid, id*2);
node R = getMax(u, v, mid+1, r, id*2+1);
if (L.x==-1)
return R;
if (R.x==-1)
return L;
return max(L, R);
}
node getMin(int u, int v, int l, int r, int id) {
if (v<l || u>r)
return node(-1, -1, -1);
if (u<=l && r<=v)
return tr[id].second;
int mid = (l + r) / 2;
node L = getMin(u, v, l, mid, id*2);
node R = getMin(u, v, mid+1, r, id*2+1);
if (L.x==-1)
return R;
if (R.x==-1)
return L;
return min(L, R);
}
void upd(int pos, node val) {
upd(compVal[pos], val, 1, sizeOfTree, 1);
}
node getMax(int u, int v) {
return getMax(u, v, 1, sizeOfTree, 1);
}
node getMin(int u, int v) {
return getMin(u, v, 1, sizeOfTree, 1);
}
} tr;
struct vertex {
int val, lazy;
vertex *L, *R;
vertex() {
val = lazy = -INF;
L = NULL; R = NULL;
}
void createChild() {
if (L==NULL) {
L = new vertex();
R = new vertex();
}
}
};
struct dynamicSegmenTree {
vertex *root;
void init() {
root = new vertex();
}
void down(vertex *u) {
u->createChild();
vertex *v1 = u->L, *v2 = u->R;
v1->val = max(v1->val, u->lazy);
v1->lazy = max(v1->lazy, u->lazy);
v2->val = max(v2->val, u->lazy);
v2->lazy = max(v2->lazy, u->lazy);
u->lazy = -INF;
}
void upd(int u, int v, int val, int l, int r, vertex *cur) {
if (v<l || u>r)
return;
if (u<=l && r<=v) {
cur->val = max(cur->val, val);
cur->lazy = max(cur->lazy, val);
return;
}
down(cur);
int mid = (l + r) / 2;
cur->createChild();
upd(u, v, val, l, mid, cur->L);
upd(u, v, val, mid+1, r, cur->R);
cur->val = max(cur->L->val, cur->R->val);
}
int get(int pos, int l, int r, vertex *cur) {
if (pos<l || pos>r)
return -INF;
if (pos==l && r==pos)
return cur->val;
down(cur);
cur->createChild();
int mid = (l + r) / 2;
return max(get(pos, l, mid, cur->L),
get(pos, mid+1, r, cur->R));
}
void upd(int u, int v, int val) {
upd(u, v, val, 1, INF, root);
}
int get(int pos) {
return get(pos, 1, INF, root);
}
} T[500];
void enter() {
cin >> n >> nType >> nQuery;
for (int i=1; i<=n; ++i) {
int x, t, a, b;
cin >> x >> t >> a >> b;
storeType[t].push_back(store(x, a, b));
}
for (int i=1; i<=nQuery; ++i) {
cin >> q[i].x >> q[i].y;
q[i].id = i;
}
}
void compress() {
vector<int> container;
container.push_back(1);
for (int i=1; i<=nType; ++i) {
for (int j=0; j<storeType[i].size(); ++j) {
container.push_back(storeType[i][j].a);
container.push_back(storeType[i][j].b+1);
}
}
for (int i=1; i<=nQuery; ++i)
container.push_back(q[i].y);
sort(container.begin(), container.end());
for (int i=0; i<container.size(); ++i) {
if (i==0 || container[i]!=container[i-1])
++nVal;
compVal[container[i]] = nVal;
}
}
void init_store(int id, bool leftside, vector<rect> &queryContainer) {
tr.init(nVal);
sort(storeType[id].begin(), storeType[id].end());
int t = -1;
if (leftside) {
reverse(storeType[id].begin(), storeType[id].end());
t *= -1;
tr.upd(1, node(1, INF, -2*INF));
}
else {
tr.upd(1, node(1, INF, 2*INF));
}
for (int i=(int)storeType[id].size()-1; i>=0; --i) {
int a = storeType[id][i].a, b = storeType[id][i].b, x = storeType[id][i].x;
node L = tr.getMax(compVal[a], compVal[b]);
node R = tr.getMax(1, compVal[a]);
if (R.b>=b) {
queryContainer.push_back(rect(x, (x+R.x+leftside)/2, a, b, t*x));
tr.upd(R.a, node(R.a, a-1, R.x));
tr.upd(b+1, node(b+1, R.b, R.x));
tr.upd(a, node(a, b, x));
continue;
}
if (R.b>=a) {
queryContainer.push_back(rect(x, (R.x+x+leftside)/2, a, R.b, t*x));
tr.upd(R.a, node(R.a, a-1, R.x));
}
if (L.b>=b) {
queryContainer.push_back(rect(x, (x+L.x+leftside)/2, b, L.a, t*x));
tr.upd(b+1, node(b+1, L.b, L.x));
}
while (true) {
node M = tr.getMin(compVal[a], compVal[b]);
if (M.x==-1)
break;
queryContainer.push_back(rect(x, (x+M.x+leftside)/2, M.a, M.b, t*x));
tr.upd(M.a, node(-1, -1, -1));
}
tr.upd(a, node(a, b, x));
}
}
void add_invalid_year(int id) {
tmp.clear();
for (int i=0; i<storeType[id].size(); ++i) {
tmp.push_back(make_pair(compVal[storeType[id][i].a], 1));
tmp.push_back(make_pair(compVal[storeType[id][i].b+1], -1));
}
sort(tmp.begin(), tmp.end());
int cnt = 0;
for (int i=0; i+1<tmp.size(); ++i) {
cnt += tmp[i].second;
if (cnt>0) {
ps[tmp[i].first]++;
ps[tmp[i+1].first]--;
}
}
}
void sqrt_decomposition() {
for (int i=1; i<=nQuery; ++i) {
block[nBlock].push_back(q[i]);
if (i<=n && i%blockSize==0)
++nBlock;
}
for (int i=1; i<=nBlock; ++i) {
sort(block[i].begin(), block[i].end());
xMin[i] = block[i][0].x;
xMax[i] = block[i].back().x;
}
}
void process_query(vector<rect> r, int res[]) {
for (int i=1; i<=nBlock; ++i)
T[i].init();
for (int i=1; i<=nQuery; ++i)
res[i] = -INF;
for (int i=0; i<r.size(); ++i) {
int x1 = r[i].x1, x2 = r[i].x2;
int y1 = r[i].y1, y2 = r[i].y2;
int val = r[i].val;
for (int j=1; j<=nBlock; ++j) {
if (xMin[j]>x2 || xMax[j]<x1)
continue;
if (x1<=xMin[j] && xMax[j]<=x2) {
T[j].upd(y1, y2, val);
}
else {
for (int k=0; k<block[j].size(); ++k)
if (x1<=block[j][k].x && block[j][k].x<=x2
&& y1<=block[j][k].y && block[j][k].y<=y2)
res[block[j][k].id] = max(res[block[j][k].id], val);
}
}
}
for (int i=1; i<=nBlock; ++i) {
for (int j=0; j<block[i].size(); ++j) {
res[block[i][j].id] = max(res[block[i][j].id], T[i].get(block[i][j].y));
}
}
}
int main() {
//freopen(FILE_NAME".inp", "r", stdin);
//freopen(FILE_NAME".out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0);
enter();
compress();
for (int i=1; i<=nType; ++i) {
init_store(i, false, rectRight);
init_store(i, true, rectLeft);
add_invalid_year(i);
}
for (int i=1; i<=nVal; ++i)
ps[i] += ps[i-1];
sqrt_decomposition();
process_query(rectRight, res1);
process_query(rectLeft, res2);
for (int i=1; i<=nQuery; ++i) {
int x = q[i].x, y = q[i].y, id = q[i].id;
if (ps[compVal[y]]!=nType)
res[id] = -1;
else
res[id] = max(x+res1[id], res2[id]-x);
}
for (int i=1; i<=nQuery; ++i) {
cout << max(-1, res[i]) << '\n';
}
}
Compilation message
new_home.cpp: In function 'void compress()':
new_home.cpp:236:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<storeType[i].size(); ++j) {
~^~~~~~~~~~~~~~~~~~~~
new_home.cpp:244:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<container.size(); ++i) {
~^~~~~~~~~~~~~~~~~
new_home.cpp: In function 'void add_invalid_year(int)':
new_home.cpp:295:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<storeType[id].size(); ++i) {
~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:301:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i+1<tmp.size(); ++i) {
~~~^~~~~~~~~~~
new_home.cpp: In function 'void process_query(std::vector<rect>, int*)':
new_home.cpp:326:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i=1; i<=nQuery; ++i)
^~~
new_home.cpp:328:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i=0; i<r.size(); ++i) {
^~~
new_home.cpp:328:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<r.size(); ++i) {
~^~~~~~~~~
new_home.cpp:339:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k=0; k<block[j].size(); ++k)
~^~~~~~~~~~~~~~~~
new_home.cpp:347:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<block[i].size(); ++j) {
~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
7544 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7664 KB |
Output is correct |
| 3 |
Correct |
10 ms |
7664 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
7752 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
7544 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7664 KB |
Output is correct |
| 3 |
Correct |
10 ms |
7664 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
7752 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5081 ms |
59324 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
727 ms |
158144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
7544 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7664 KB |
Output is correct |
| 3 |
Correct |
10 ms |
7664 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
7752 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
7544 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7664 KB |
Output is correct |
| 3 |
Correct |
10 ms |
7664 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
7752 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
