Submission #397905

#	Time	Username	Problem	Language	Result	Execution time	Memory
397905		ritul_kr_singh	Untitled (POI11_tem)	C++17	83 / 100	1097 ms	15428 KiB

Main

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'

const int INF = 2e9;

struct FenwickTree{
	vector<int> a; int n, s;
	FenwickTree(int N){ a.assign((n=N)+1, -INF); }
	void update(int i, int v){
		for(++i; i<=n; i+=i&-i) a[i] = max(a[i], v);
	}
	int get(int i){
		s = -INF;
		for(++i; i>=1; i-=i&-i) s = max(s, a[i]);
		return s;
	}
};

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];
 
	FenwickTree a(n+1), b(n+1);
	
	for(int i=n-1; i>=0; --i){
		int j = n;
		int low = i, high = n-1;
		while(low < high){
			int mid = (low + high) / 2;
			if(a.get(mid+1) <= l[i]) low = mid+1;
			else high = mid;
		}
		j = min(j, low+1);
		low = i, high = n-1;
		while(low < high){
			int mid = (low + high) / 2;
			if(b.get(mid+1) <= -l[i]) low = mid+1;
			else high = mid;
		}
		j = min(j, low+1);
		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);	
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 0 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 0 / 9
• Subtask 12: 9 / 9