Submission #397874

#TimeUsernameProblemLanguageResultExecution timeMemory
397874ritul_kr_singhUntitled (POI11_tem)C++17
50 / 100
772 ms44732 KiB
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'

const int INF = 2e9;

struct SegmentTree{
	vector<int> a; int sz = 1;
	SegmentTree(int n){
		while(sz < n) sz += sz;
		a.assign(2*sz, -INF);
	}
	void update(int i, int v, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = v);
		int mx = (lx + rx) / 2;
		if(i < mx) update(i, v, 2*x+1, lx, mx);
		else update(i, v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int v){ update(i, v, 0, 0, sz); }
	int firstGreater(int v, int x, int lx, int rx){
		if(rx-lx==1) return lx;
		int mx = (lx + rx) / 2;
		if(a[2*x+1] > v) return firstGreater(v, 2*x+1, lx, mx);
		else return firstGreater(v, 2*x+2, mx, rx);
	}
	int firstGreater(int v){ return firstGreater(v, 0, 0, sz); }
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	int l[n], r[n];

	for(int i=0; i<n; ++i) cin >> l[i] >> r[i];

	SegmentTree a(n+1), b(n+1);
	
	for(int i=n-1; i>=0; --i){
		int j = min(a.firstGreater(l[i]), b.firstGreater(-l[i]));
		j = min(j, n);
		a.update(i, l[i]);
		b.update(i, -r[i]);
		r[i] = j - i;
		if(j < n && l[i] < l[j]) r[i] += r[j];
	}

	cout << *max_element(r, r+n);	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...