제출 #1157118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157118		kerem	Osumnjičeni (COCI21_osumnjiceni)	C++20	110 / 110	560 ms	13908 KiB

Main

#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e18+1
#define N 500
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed<<setprecision(0)
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;


void solve(){
	int n;
	cin >> n;
	vector<pii> d,h;
	vector<int> a;
	set<pii> s;
	d.assign(n+5,pii());
	h.assign(n+5,pii());
	a.assign(n+5,0);
	for(int i=1;i<=n;i++)
		cin >> h[i].fr >> h[i].sc;
	int j=1;
	for(int i=1;i<=n;i++){
		if(j<=n){
			auto it=s.upper_bound(h[j]);
			while(j<=n && (it==s.end() || h[j].sc<it->fr) && (it==s.begin() || (--it)->sc<h[j].fr)){
				s.insert(h[j]);
				j++;
				it=s.upper_bound(h[j]);
			}
		}
		a[i]=j;
		s.erase(h[i]);
	}
	d[n+1].fr=n+1;
	d[n+1].sc=0;
	for(int i=n;i>=1;i--){
		if(i/N==a[i]/N){
			d[i].fr=d[a[i]].fr;
			d[i].sc=d[a[i]].sc+1;
		}
		else{
			d[i].fr=a[i];
			d[i].sc=1;
		}
	}
	int q;
	cin >> q;
	while(q--){
		int l,r;
		cin >> l >> r;
		int ans=0;
		while(l/N<r/N){
			ans+=d[l].sc;
			l=d[l].fr;
		}
		while(l<=r){
			ans++;
			l=a[l];
		}
		cout << ans << endl;
	}
}     
int32_t main(){
	//~ freopen("a.txt","r",stdin);
	fast;
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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