#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)3e5 + 5;
const int inf = (int)1e9;
map<int, int> cnt[N];
int x[N], t[N], a[N], b[N];
vector<int> cors;
struct lin{
int tt;
int lef;
int rig;
int dir;
int val;
int add;
bool operator< (const lin &aq) const {
return tt < aq.tt;
}
};
int cur;
vector<lin> lis;
void segm(int li, int ri, int mod){
lis.push_back({cur, li, (li + ri) / 2, 0, -li, mod});
lis.push_back({cur, (li + ri) / 2, ri, 1, ri, mod});
cors.push_back((li + ri) / 2);
}
void add(int typ, int v){
cnt[typ][v] ++ ;
auto it = cnt[typ].find(v);
auto nx = it;
auto pv = it;
nx ++ ;
pv -- ;
segm(pv->fi, nx->fi, 1);
segm(pv->fi, it->fi, 0);
segm(it->fi, nx->fi, 0);
}
void del(int typ, int v){
auto it = cnt[typ].find(v);
auto nx = it;
auto pv = it;
nx ++ ;
pv -- ;
segm(pv->fi, it->fi, 1);
segm(it->fi, nx->fi, 1);
segm(pv->fi, nx->fi, 0);
cnt[typ][v] -- ;
if(cnt[typ][v] == 0){
cnt[typ].erase(v);
}
}
int xx[N];
int yr[N];
const int M = (int)2e6;
map<int, int> segt[M * 4][2];
int getid(int pp){
return lower_bound(cors.begin(), cors.end(), pp) - cors.begin();
}
int m;
void update(int node, int cl, int cr, int tl, int tr,int dir, int v, int mode){
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
if(mode == 0){
segt[node][dir][v] ++ ;
}
else{
segt[node][dir][v] -- ;
if(segt[node][dir][v] == 0){
segt[node][dir].erase(v);
}
}
return;
}
int mid = (cl + cr) / 2;
update(node * 2, cl, mid, tl, tr, dir, v, mode);
update(node * 2 + 1, mid + 1, cr, tl, tr, dir, v, mode);
}
int get(int node, int cl, int cr, int pos){
int vl = 0;
if(!segt[node][0].empty()){
auto it = segt[node][0].end();
-- it;
vl = max(vl, (it->fi) + cors[pos]);
}
if(!segt[node][1].empty()){
auto it = segt[node][1].end();
-- it;
vl = max(vl, (it->fi) - cors[pos]);
}
if(cl == cr) return vl;
int mid = (cl + cr) / 2;
if(mid >= pos)
return max(vl, get(node * 2, cl, mid, pos));
else
return max(vl, get(node * 2 + 1, mid + 1, cr, pos));
}
int soln[N];
int main(){
fastIO;
int n, k, q;
cin >> n >> k >> q;
vector<pii> eve;
for(int i = 1; i <= n; i ++ ){
cin >> x[i] >> t[i] >> a[i] >> b[i];
x[i] *= 2;
cors.push_back(x[i]);
eve.push_back(mp(a[i], i));
eve.push_back(mp(b[i] + 1, i));
}
vector<pii> ord;
for(int i = 1; i <= q; i ++ ){
cin >> xx[i] >> yr[i];
xx[i] *= 2;
cors.push_back(xx[i]);
ord.push_back(mp(yr[i], i));
}
sort(ord.begin(), ord.end());
sort(eve.begin(), eve.end());
for(int i = 1; i <= k ; i ++ ){
cnt[i][-inf] ++ ;
cnt[i][inf] ++ ;
segm(-inf, inf, 0);
}
for(int i = 0 ; i < eve.size(); i ++ ){
cur = eve[i].fi;
if(cur == a[eve[i].se]){
add(t[eve[i].se], x[eve[i].se]);
}
else{
del(t[eve[i].se], x[eve[i].se]);
}
}
sort(cors.begin(), cors.end());
cors.resize(unique(cors.begin(), cors.end()) - cors.begin());
m = cors.size();
int it = 0;
int gq;
for(int i = 0; i < q ; i ++ ){
while(it < lis.size() && lis[it].tt <= ord[i].fi){
update(1, 0, m - 1, getid(lis[it].lef), getid(lis[it].rig), lis[it].dir, lis[it].val, lis[it].add);
it ++ ;
}
gq = get(1, 0, m - 1, getid(xx[ord[i].se]));
gq /= 2;
if(gq > (int)1e8){
soln[ord[i].se] = -1;
}
else{
soln[ord[i].se] = gq;
}
}
for(int i = 1; i <= q; i ++ ){
cout << soln[i] << "\n";
}
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for(int i = 0 ; i < eve.size(); i ++ ){
| ~~^~~~~~~~~~~~
new_home.cpp:165:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<lin>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | while(it < lis.size() && lis[it].tt <= ord[i].fi){
| ~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
539 ms |
765932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
539 ms |
765932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4897 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5170 ms |
978636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
539 ms |
765932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
539 ms |
765932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
