Submission #397870

#	Time	Username	Problem	Language	Result	Execution time	Memory
397870		ritul_kr_singh	Untitled (POI11_tem)	C++17	0 / 100	766 ms	45424 KiB

Main

#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], dp[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]));
		dp[i] = j - i;
		if(j < n && l[i] < l[j]) dp[i] += dp[j];
		a.update(i, l[i]);
		b.update(i, -r[i]);
	}

	cout << *max_element(dp, dp+n);	
}

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