#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair < int, int > pii;
const int N = 3e5 + 500;
const int OFF = (1 << 20);
const int KRJ = 1e8;
int zadL[N], zadR[N];
int x[N], ty[N], a[N], b[N], lst_op[N];
int kd[N], gdje[N], n, q, k;
set < pii > S[N];
vector < int > saz;
vector < pair < pii, pii > > s_l, s_r;
vector < int > red;
bool cmp(int A, int B){
return kd[A] < kd[B];
}
bool fl = 0; int NULA = -KRJ;
int tour[2 * OFF], ans[N], neee[OFF];
void sazmi(){
for(int i = 0;i < q;i++)
saz.PB(kd[i]);
for(int i = 1;i <= n;i++)
saz.PB(a[i]), saz.PB(b[i]);
sort(saz.begin(), saz.end());
saz.erase(unique(saz.begin(), saz.end()), saz.end());
for(int i = 0;i < q;i++)
kd[i] = lower_bound(saz.begin(), saz.end(), kd[i]) - saz.begin();
for(int i = 1;i <= n;i++){
a[i] = lower_bound(saz.begin(), saz.end(), a[i]) - saz.begin();
b[i] = lower_bound(saz.begin(), saz.end(), b[i]) - saz.begin();
}
}
void pocisti(){
for(int i = 0;i < 2 * OFF;i++)
tour[i] = NULA;
}
int mrg(int A,int B){
if(!fl)
return max(A, B);
return min(A, B);
}
void update(int i, int a, int b, int lo, int hi, int x){
if(lo <= a && b <= hi){
tour[i] = mrg(tour[i], x);
return;
}
if(a > hi || b < lo) return;
update(2 * i, a, (a + b) / 2, lo, hi, x);
update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
}
int query(int i){
int ret = NULA;
for(i = i + OFF; i ; i /= 2)
ret = mrg(ret, tour[i]);
return ret;
}
void dodaj_brid(int l, int r,int trn, int tip){
//printf("dodajem brid između %d i %d u %d tipa %d\n", l, r, trn, tip);
if(l == 0 && r == n + 1){
neee[lst_op[tip]]++;
neee[trn]--;
//printf("zabrana od %d do %d\n", lst_op[tip], trn);
}
else if(l == 0){
s_l.PB({{0, x[r]}, {zadL[r], trn - 1}});
//printf("brid s_l u kor %d dodajem kor %d na interval %d %d\n", 0, x[r], zadL[r], trn - 1);
zadL[r] = trn;
}
else if(r == n + 1){
s_r.PB({{KRJ, x[l]}, {zadR[l], trn - 1}});
//printf("brid s_r u kor %d dodajem kor %d na interval %d %d\n", KRJ, x[l], zadR[l], trn - 1);
zadR[l] = trn;
}
else{
s_l.PB({{(x[l] + x[r] + 1) / 2, x[r]}, {zadL[r], trn - 1}});
s_r.PB({{(x[l] + x[r]) / 2, x[l]}, {zadR[l], trn - 1}});
//printf("brid s_l u kor %d dodajem kor %d na interval %d %d\n", (x[l] + x[r] + 1) / 2, x[r], zadL[r], trn - 1);
//printf("brid s_r u kor %d dodajem kor %d na interval %d %d\n", (x[l] + x[r]) / 2, x[l], zadR[l], trn - 1);
zadR[l] = trn, zadL[r] = trn;
}
}
void ubaci(int i, int trn){
int l = 0, r = n + 1;
if(S[ty[i]].lower_bound({x[i], i}) != S[ty[i]].begin())
l = (--S[ty[i]].lower_bound({x[i], i})) -> Y;
if(S[ty[i]].lower_bound({x[i], i}) != S[ty[i]].end())
r = S[ty[i]].lower_bound({x[i],i}) -> Y;
dodaj_brid(l, r, trn, ty[i]);
S[ty[i]].insert({x[i], i});
}
void izbaci(int i, int trn){
S[ty[i]].erase({x[i], i});
lst_op[ty[i]] = trn;
int l = 0, r = n + 1;
if(S[ty[i]].lower_bound({x[i], i}) != S[ty[i]].begin())
l = (--S[ty[i]].lower_bound({x[i], i})) -> Y;
if(S[ty[i]].lower_bound({x[i], i}) != S[ty[i]].end())
r = S[ty[i]].lower_bound({x[i], i}) -> Y;
dodaj_brid(l, i, trn, ty[i]);
dodaj_brid(i, r, trn, ty[i]);
}
void gradi_bridove(){
vector < pii > kda;
for(int i = 1;i <= n;i++){
kda.PB({a[i], i});
kda.PB({b[i] + 1, -i});
}
sort(kda.begin(), kda.end());
for(pii cur : kda){
if(cur.Y > 0)
ubaci(cur.Y, cur.X);
else
izbaci(-cur.Y, cur.X);
}
for(int i = 1;i <= k;i++)
neee[lst_op[i]]++;
for(int i = 1;i < OFF;i++)
neee[i] += neee[i - 1];
}
void racunaj(){
for(int i = 0;i < q;i++)
red.PB(i);
sort(red.begin(), red.end(), cmp);
sort(s_l.begin(), s_l.end());
sort(s_r.begin(), s_r.end());
int j = 0;
pocisti();
for(int i = 0;i < q;i++){
int x = red[i];
while(j < (int)s_l.size() && s_l[j].X.X <= gdje[x]){
update(1, 0, OFF - 1, s_l[j].Y.X, s_l[j].Y.Y, s_l[j].X.Y);
j++;
}
ans[x] = max(ans[x], query(kd[x]) - gdje[x]);
}
fl = 1; NULA = 2 * KRJ;
pocisti();
reverse(red.begin(), red.end());
j = 0;
for(int i = 0;i < q;i++){
int x = red[i];
while(j < (int)s_r.size() && s_r[j].X.X >= gdje[x]){
update(1, 0, OFF - 1, s_r[j].Y.X, s_r[j].Y.Y, s_r[j].X.Y);
j++;
}
ans[x] = max(ans[x], gdje[x] - query(kd[x]));
}
}
int main(){
scanf("%d%d%d", &n, &k, &q);
for(int i = 1;i <= n;i++)
scanf("%d%d%d%d", x + i, ty + i, a + i, b + i);
for(int i = 0;i < q;i++)
scanf("%d%d", gdje + i, kd + i);
sazmi();
//for(int i = 1;i <= n;i++)
// printf("ducan[ %d ] traje od %d do %d na poz %d\n", ty[i], a[i], b[i], x[i]);
//for(int i = 0;i < q;i++)
// printf("hm? mogao bi izgraditi kucu %d godine gospodnje na poz %d\n", kd[i], gdje[i]);
gradi_bridove();
racunaj();
for(int i = 0;i < q;i++){
if(neee[kd[i]])
printf("-1\n");
else
printf("%d\n", ans[i]);
}
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:175:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &k, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", x + i, ty + i, a + i, b + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:179:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", gdje + i, kd + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
26752 KB |
Output is correct |
| 2 |
Correct |
19 ms |
26752 KB |
Output is correct |
| 3 |
Correct |
18 ms |
26752 KB |
Output is correct |
| 4 |
Incorrect |
19 ms |
26752 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
26752 KB |
Output is correct |
| 2 |
Correct |
19 ms |
26752 KB |
Output is correct |
| 3 |
Correct |
18 ms |
26752 KB |
Output is correct |
| 4 |
Incorrect |
19 ms |
26752 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1012 ms |
93248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1709 ms |
97612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
26752 KB |
Output is correct |
| 2 |
Correct |
19 ms |
26752 KB |
Output is correct |
| 3 |
Correct |
18 ms |
26752 KB |
Output is correct |
| 4 |
Incorrect |
19 ms |
26752 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
26752 KB |
Output is correct |
| 2 |
Correct |
19 ms |
26752 KB |
Output is correct |
| 3 |
Correct |
18 ms |
26752 KB |
Output is correct |
| 4 |
Incorrect |
19 ms |
26752 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
