Submission #918118

#	Time	Username	Problem	Language	Result	Execution time	Memory
918118		dsyz	Osumnjičeni (COCI21_osumnjiceni)	C++17	0 / 110	64 ms	21248 KiB

Main

#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 (stderr)

Main.cpp: In function 'int main()':
Main.cpp:48:6: warning: unused variable 'L' [-Wunused-variable]
   48 |   ll L = arr[u].first.first;
      |      ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50