#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (200005)
ll N,Q;
ll parent[MAXN];
ll find_set(ll x){
if(parent[x] == x) return x;
parent[x] = find_set(parent[x]);
return parent[x];
}
bool same_set(ll x,ll y){
return find_set(x) == find_set(y);
}
void merge_set(ll x,ll y){
parent[find_set(x)] = find_set(y);
}
ll fw[MAXN];
void update(int x,ll nval){
x++; //make it 1-indexed
for(;x<MAXN;x+=x&(-x)) fw[x]+=nval;
}
ll aaa(ll x){
ll res = 0;
for(;x;x-=x&(-x)) res += fw[x];
return res;
}
ll sum(ll a,ll b){
a++, b++; //make it 1-indexed
return aaa(b) - aaa(a-1);
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>N;
pair<pair<ll,ll>,ll> arr[N];
for(ll i = 0;i < N;i++){
ll l,r;
cin>>l>>r;
arr[i] = {{l,r},i};
}
sort(arr,arr + N);
for(ll i = 0;i < N;i++){
parent[i] = i;
}
ll maxiR[N]; //maximum R[i] in the connected component of node i
memset(maxiR,-1,sizeof(maxiR));
for(ll u = 0;u < N;u++){
ll L = arr[u].first.first;
ll R = arr[u].first.second;
ll ind = arr[u].second;
maxiR[ind] = max(maxiR[ind],R);
if(u < N - 1){
if(maxiR[ind] >= arr[u + 1].first.first){
merge_set(ind,arr[u + 1].second);
maxiR[arr[u + 1].second] = max(maxiR[ind],arr[u + 1].first.second);
}
}
}
deque<pair<ll,ll> > sweep;
ll previngroup[N], nearestleft[N];
memset(previngroup,-1,sizeof(previngroup));
memset(nearestleft,-1,sizeof(nearestleft));
for(ll i = 0;i < N;i++){
ll groupind = find_set(i);
nearestleft[i] = previngroup[groupind];
sweep.push_back({nearestleft[i] + 1,i});
previngroup[groupind] = i;
}
sort(sweep.begin(),sweep.end());
cin>>Q;
vector<pair<pair<ll,ll>,ll> > qu;
for(ll q = 0;q < Q;q++){
ll a,b;
cin>>a>>b;
a--, b--;
qu.push_back({{a,b},q});
}
sort(qu.begin(),qu.end());
ll ans[Q];
for(auto u : qu){
ll a = u.first.first;
ll b = u.first.second;
ll ind = u.second;
while(!sweep.empty() && sweep.front().first <= a){
update(sweep.front().second,1);
sweep.pop_front();
}
ans[ind] = sum(a,b);
}
for(ll q = 0;q < Q;q++){
cout<<ans[q]<<'\n';
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:48:6: warning: unused variable 'L' [-Wunused-variable]
48 | ll L = arr[u].first.first;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
20052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
21248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
20052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
