#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()
#define l first
#define r second
#define boo bool
using namespace std;
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
int n, q;
vector<pii> highway;
vector<pii> segm;
vector<int> rez;
vector<pii> bruteqs;
const int nmax = 1e5 + 5;
boo intersect(pii a, pii b) {
return !(a.r < b.l || b.r < a.l);
}
boo intersecc(pii a, pii b) {
return a.l <= b.r && b.r <= a.r;
}
#define lsb(x) (x & -x)
struct AIB {
int tree[nmax];
int len;
void init(int nlen) {
len = nlen;
memset(tree, 0, sizeof(tree[0]) * (len + 1));
}
void upd(int p, int x = 1) {
while(p <= len)
tree[p] += x,
p += lsb(p);
}
int query(int p) {
int sum = 0;
while(p > 0)
sum += tree[p],
p -= lsb(p);
return sum;
}
int query(int l, int r) { return query(r) - query(l - 1); }
};
namespace Driver {
void solve(vector<int> V) {
vector<tii> aggr;
vector<int> tmprez(q, 0);
vector<int> spart(sz(highway));
for(int i = 1; i < sz(highway); i++)
if(highway[i].l > highway[i - 1].r)
spart[i] = spart[i - 1] + 1;
else
spart[i] = spart[i - 1];
for(int i = 0; i < sz(V); i++) {
auto [f, s] = bruteqs[V[i]];
int lim1 = 0;
for(int i = 16; i >= 0; i--) {
if(lim1 + (1 << i) >= highway.size()) continue;
if(highway[lim1 + (1 << i)].l <= segm[f].r)
lim1 += (1 << i);
}
int lim2 = 0;
for(int i = 16; i >= 0; i--) {
if(lim2 + (1 << i) >= highway.size()) continue;
if(highway[lim2 + (1 << i)].r < segm[s].l)
lim2 += (1 << i);
}
lim2++;
//cerr << lim1 << ' ' << lim2 << '\n';
//cerr << f << ' ' << s << "\n";
//cerr << highway[lim1].l << ' ' << highway[lim1].r << '\t' << highway[lim2].l << ' ' << highway[lim2].r << "\n";
//cerr << segm[f].l << ' ' << segm[f].r << '\t' << segm[s].l << ' ' << segm[s].r << "\n\n";
if(spart[lim2] - spart[lim1] > 0) {
rez[V[i]] = 0;
swap(V[i], V.back());
V.pop_back();
i--;
continue;
}
if(intersecc(segm[s], highway[lim2]) && intersecc(highway[lim1], segm[f])) {
rez[V[i]] = lim2 - lim1 + 2;
//cerr << "here\n";
//cerr << rez[0] << '\n';
swap(V[i], V.back());
V.pop_back();
i--;
continue;
}
int l1, r1, l2, r2;
tie(l2, r2) = segm[s];
tie(l1, r1) = highway[lim2 - 1];
aggr.emplace_back(l1 - 1, l2, -r2);
aggr.emplace_back(r1, l2, r2);
//cerr << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
}
vector<int> ind(sz(aggr));
iota(all(ind), 0);
//for(auto &x : ind) x /= 2;
sort(all(ind), [&](auto a, auto b) { return aggr[a] < aggr[b]; });
vector<pii> cpsegm = segm;
sort(all(cpsegm));
AIB aib;
aib.init(2 * n);
auto advance = [&](int& ptr) {
int atr = V[ind[ptr] / 2];
auto [line, l, r] = aggr[ind[ptr]];
if(r < 0) {
r = -r;
tmprez[atr] = -aib.query(l, r);
}
else {
tmprez[atr] += aib.query(l, r);
if(tmprez[atr] == 0)
rez[atr] = 0;
else
rez[atr]++;
}
ptr++;
};
int ptr = 0;
for(auto [x, y] : cpsegm) {
while(ptr < sz(ind) && get<0>(aggr[ind[ptr]]) < x)
advance(ptr);
aib.upd(y);
}
while(ptr < sz(ind)) {
advance(ptr);
}
return;
}
}
int main() {
cin >> n >> q;
segm.resize(n);
vector<int> ind(n);
iota(all(ind), 0);
map<int,int> nrm;
for(auto &[a, b] : segm) cin >> a >> b, nrm[a], nrm[b];
int cnt = 1; for(auto &[a, b] : nrm) b = cnt++;
for(auto &[a, b] : segm) tie(a, b) = pii{nrm[a], nrm[b]};
sort(all(ind), [&](int a, int b) { return segm[a].l < segm[b].l || (segm[a].l == segm[b].l && segm[a].r > segm[b].r); });
highway.emplace_back(-1, -1);
for(auto i : ind) {
if(highway.size() == 1 || (highway.size() >= 2 && segm[i].l > highway.rbegin()[1].r && segm[i].r > highway.back().r))
highway.emplace_back(segm[i]);
else if(highway.back().r < segm[i].r)
highway.back() = segm[i];
}
//for(auto [a, b] : highway) cerr << a << ' ' << b << '\n';
vector<int> tosolve;
bruteqs.resize(q);
for(auto &[a, b] : bruteqs) {
cin >> a >> b;
--a;
--b;
if(segm[a].r > segm[b].r)
rez.push_back(0);
else if(segm[a] == segm[b])
rez.push_back(-1);
else if(intersect(segm[a], segm[b]))
rez.push_back(1);
else {
tosolve.push_back(rez.size());
rez.push_back(0);
}
}
Driver::solve(tosolve);
for(auto x : rez) {
if(x == 0) cout << "impossible\n";
else if(x == -1) cout << "0\n";
else cout << x << '\n';
}
}
Compilation message
events.cpp: In function 'void Driver::solve(std::vector<int>)':
events.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i = 1; i < sz(highway); i++)
| ^
events.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < sz(V); i++) {
| ^
events.cpp:63:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | auto [f, s] = bruteqs[V[i]];
| ^
events.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if(lim1 + (1 << i) >= highway.size()) continue;
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
events.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if(lim2 + (1 << i) >= highway.size()) continue;
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
events.cpp: In lambda function:
events.cpp:122:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
122 | auto [line, l, r] = aggr[ind[ptr]];
| ^
events.cpp: In function 'void Driver::solve(std::vector<int>)':
events.cpp:138:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
138 | for(auto [x, y] : cpsegm) {
| ^
events.cpp:139:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | while(ptr < sz(ind) && get<0>(aggr[ind[ptr]]) < x)
| ^
events.cpp:143:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | while(ptr < sz(ind)) {
| ^
events.cpp: In function 'int main()':
events.cpp:157:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
157 | for(auto &[a, b] : segm) cin >> a >> b, nrm[a], nrm[b];
| ^
events.cpp:158:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
158 | int cnt = 1; for(auto &[a, b] : nrm) b = cnt++;
| ^
events.cpp:159:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
159 | for(auto &[a, b] : segm) tie(a, b) = pii{nrm[a], nrm[b]};
| ^
events.cpp:173:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
173 | for(auto &[a, b] : bruteqs) {
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Runtime error |
258 ms |
22760 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
724 KB |
Output is correct |
| 4 |
Correct |
3 ms |
724 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
724 KB |
Output is correct |
| 4 |
Correct |
3 ms |
724 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
724 KB |
Output is correct |
| 4 |
Correct |
3 ms |
724 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
257 ms |
22872 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Runtime error |
258 ms |
22760 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
