#include <bits/stdc++.h>
using namespace std;
const int nmax = 3e5 + 5;
const int ERROR = -1e9 - 7;
//#warning SA FACI K-URILE DE LA 1 LA K !!!
namespace {
struct Shop {
int x, c, a, b;
}shop[nmax];
struct Query {
int l, y, rez = -1e9;
void operator <<= (const int& x) {
rez = (rez == ERROR? ERROR : max(rez, x));
}
} qs[nmax];
int n, q, k;
int ogn;
int maxx = 0;
namespace NORMALIZE { // de la 1
map<int,int> normt;
void normalize() {
for(int i = 0; i < n; i++)
normt[shop[i].a],normt[shop[i].b];
for(int i = 0; i < q; i++)
normt[qs[i].y];
int cnt = 1;
for(auto &x : normt)
x.second = cnt++;
for(int i = 0; i < n; i++)
shop[i].a = normt[shop[i].a], shop[i].b = normt[shop[i].b];
for(int i = 0; i < q; i++)
qs[i].y = normt[qs[i].y];
return;
}
}
namespace INVALIDATE {
vector<pair<int,int> > smen[nmax];
void invalidate() {
int temp = n;
n = ogn;
sort(shop, shop + n, [&](auto a, auto b) {return a.a < b.a;});
for(int i = 0; i < n; i++) {
if(smen[shop[i].c].size() == 0 || smen[shop[i].c].back().second < shop[i].a)
smen[shop[i].c].push_back({shop[i].a, shop[i].b});
else
smen[shop[i].c].back().second = max(smen[shop[i].c].back().second, shop[i].b);
}
vector<int> events(NORMALIZE::normt.size() + 5);
for(int i = 1; i <= k; i++) {
for(auto [a, b] : smen[i])
events[a]++, events[b + 1]--;
}
int l = 0;
for(auto &x : events)
x += l, l = x;
for(int i = 0; i < q; i++) {
if(events[qs[i].y] != k)
qs[i].rez = ERROR;
}
n = temp;
return;
}
}
namespace READ {
void read() {
cin >> n >> k >> q;
ogn = n;
for(int i = 0; i < n; i++)
cin >> shop[i].x >> shop[i].c >> shop[i].a >> shop[i].b, shop[i].x *= 2, maxx = max(maxx, shop[i].x);
for(int i = 0; i < q; i++)
cin >> qs[i].l >> qs[i].y, qs[i].l *= 2, maxx = max(qs[i].l * 2, maxx);
for(int i = 1; i <= k; i++)
shop[n].x = 6e8, shop[n].c = i, shop[n].a = -1, shop[n].b = 1e8 + 1,
n++,
shop[n].x = -6e8, shop[n].c = i, shop[n].a = -1, shop[n].b = 1e8 + 1,
n++,
maxx = 6e8;
return;
}
}
namespace AINT {
vector<int> tree;
int len;
void setup() {
tree.resize((len = NORMALIZE::normt.size() + 1) * 4);
fill(tree.begin(), tree.end(), -1e9);
}
void push(int l, int r, int val, int node = 1, int cl = 1, int cr = len) {
if(r < l)
return;
if(r < cl || cr < l)
return;
if(l <= cl && cr <= r) {
tree[node] = max(tree[node], val);
return;
}
int mid = cl + cr >> 1;
push(l, r, val, 2 * node, cl, mid);
push(l, r, val, 2 * node + 1, mid + 1, cr);
}
int query(int poz, int node = 1, int cl = 1, int cr = len) {
if(cl == cr)
return tree[node];
int mid = cl + cr >> 1;
if(poz <= mid)
return max(query(poz, 2 * node, cl, mid), tree[node]);
return max(query(poz, 2 * node + 1, mid + 1, cr), tree[node]);
}
}
struct Slope {
int x0, xmax, a, b;
bool operator < (const Slope& x) const {
return xmax < x.xmax;
}
};
namespace APPLY { // ai cout
void apply(vector<Slope> slope) {
::AINT::setup();
vector<pair<int,int> > events(slope.size() + q);
int ptr = 0;
for(int i = 0; i < slope.size(); i++)
events[ptr++] = {0, i};
for(int i = 0; i < q; i++)
events[ptr++] = {1, i};
auto getbypair = [&](pair<int,int> x) {
if(x.first == 0)
return slope[x.second].xmax;
return qs[x.second].l;
};
sort(events.begin(), events.end(),
[&](auto a, auto b) { return getbypair(a) < getbypair(b)
|| (getbypair(a) == getbypair(b) && a < b);});
int type, i;
for(auto ev : events) {
tie(type, i) = ev;
if(type == 0)
AINT::push(slope[i].a, slope[i].b, slope[i].x0);
else
qs[i] <<= AINT::query(qs[i].y) - qs[i].l;
}
}
}
namespace MAKESEGMENTS {
unordered_map<int, Slope> mp;
multiset<pair<int, int> > line[nmax];
vector<Slope> slope;
void erase(int poz, int time) {
if(poz == -1)
return;
if(mp.find(poz) != mp.end()) {
mp[poz].b = time;
slope.push_back(mp[poz]);
mp.erase(poz);
}
}
void insert(int r, int l, int time) {
if(r == -1)
return;
mp[r].a = time;
mp[r].x0 = shop[r].x;
mp[r].xmax = (shop[r].x + l) / 2;
}
void solve(int parametrudetimp = 0) {
if(slope.size())
slope.erase(slope.begin(), slope.end());
vector<tuple<int,int,int,int> >events;
for(int i = 0; i < n; i++) {
events.push_back({shop[i].a, shop[i].x, i, shop[i].c});
events.push_back({shop[i].b + 1, shop[i].x, i, -shop[i].c});
}
sort(events.begin(), events.end());
for(auto [t, x, i, c] : events) {
if(c > 0) {
if(1 <= x && x <= 2e8) {
auto r = line[c].upper_bound({x, i});
auto l = r;
--l;
erase(r -> second, t);
insert(r -> second, x, t);
insert(i, l -> first, t);
}
line[c].insert({x, i});
}
else {
c = -c;
if(1 <= x && x <= 2e8) {
auto r = line[c].upper_bound({x ,i});
auto l = r;
--l;
erase(r -> second, t);
erase(i, t);
insert(r -> second, l -> first, t);
}
line[c].erase({x, i});
}
}
APPLY::apply(slope);
if(parametrudetimp == 0) {
//#error fa revese
for(int i = 0; i < n; i++)
shop[i].x = maxx - shop[i].x;
for(int i = 0; i < q; i++)
qs[i].l = maxx - qs[i].l;
solve(parametrudetimp + 1);
}
return;
}
}
namespace PRINT {
void print() {
for(int i = 0; i < q; i++)
cout << (qs[i].rez == ERROR? -1 : qs[i].rez / 2) << '\n';
return;
}
}
};
int main() {
::READ::read();
::NORMALIZE::normalize();
::INVALIDATE::invalidate();
::MAKESEGMENTS::solve();
::PRINT::print();
}
Compilation message
new_home.cpp: In function 'void {anonymous}::INVALIDATE::invalidate()':
new_home.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for(auto [a, b] : smen[i])
| ^
new_home.cpp: In function 'void {anonymous}::AINT::push(int, int, int, int, int, int)':
new_home.cpp:98:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | int mid = cl + cr >> 1;
| ~~~^~~~
new_home.cpp: In function 'int {anonymous}::AINT::query(int, int, int, int)':
new_home.cpp:105:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int mid = cl + cr >> 1;
| ~~~^~~~
new_home.cpp: In function 'void {anonymous}::APPLY::apply(std::vector<{anonymous}::Slope>)':
new_home.cpp:122:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<{anonymous}::Slope>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int i = 0; i < slope.size(); i++)
| ~~^~~~~~~~~~~~~~
new_home.cpp: In function 'void {anonymous}::MAKESEGMENTS::solve(int)':
new_home.cpp:173:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
173 | for(auto [t, x, i, c] : events) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
24908 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24920 KB |
Output is correct |
| 3 |
Correct |
12 ms |
24908 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
24856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
24908 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24920 KB |
Output is correct |
| 3 |
Correct |
12 ms |
24908 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
24856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
558 ms |
59920 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
576 ms |
59804 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
24908 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24920 KB |
Output is correct |
| 3 |
Correct |
12 ms |
24908 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
24856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
24908 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24920 KB |
Output is correct |
| 3 |
Correct |
12 ms |
24908 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
24856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
