oj.uz

Submission #397905

# Submission time Handle Problem Language Result Execution time Memory
397905 2021-05-03T11:18:08 Z ritul_kr_singh Temperature (POI11_tem) C++17
83 / 100
 1000 ms 15428 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 316 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 460 KB Output is correct
2 Correct 12 ms 556 KB Output is correct
3 Correct 8 ms 588 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 8644 KB Output is correct
2 Correct 559 ms 9636 KB Output is correct
3 Correct 546 ms 10628 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 12804 KB Output is correct
2 Correct 928 ms 13632 KB Output is correct
3 Correct 932 ms 13380 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 13428 KB Output is correct
2 Correct 870 ms 14052 KB Output is correct
3 Correct 966 ms 13068 KB Output is correct

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 14296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 13096 KB Output is correct
2 Correct 936 ms 14300 KB Output is correct
3 Correct 865 ms 13668 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 14204 KB Output is correct
2 Correct 783 ms 14292 KB Output is correct
3 Correct 842 ms 14104 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 13732 KB Output is correct
2 Correct 888 ms 15136 KB Output is correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 12996 KB Output is correct
2 Execution timed out 1091 ms 15428 KB Time limit exceeded

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 12612 KB Output is correct
2 Correct 896 ms 13752 KB Output is correct