oj.uz

답안 #397911

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397911 2021-05-03T11:33:42 Z ritul_kr_singh Temperature (POI11_tem) C++17
100 / 100
 347 ms 12000 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;
	}
	int lower(int v){
		int i = 0;
		for(s=1<<20; s; s/=2) if(i+s<=n && a[i+s]<v) i+=s;
		return i;
	}
};

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 b(n+1);
	vector<int> s;
	
	for(int i=n-1; i>=0; --i){
		int low = b.lower(-l[i]+1);
		int j = min(n, low);
		b.update(i, -r[i]);
		r[i] = j - i;
 
		while(!s.empty() and l[s.back()] <= l[i]) s.pop_back();
 
		if(!s.empty() && s.back() < j) r[i] = r[s.back()] + (int)s.back() - i;
 
		s.push_back(i);
	}
 
	cout << *max_element(r, r+n);	
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 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

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 428 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 4 ms 460 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 5668 KB Output is correct
2 Correct 143 ms 6436 KB Output is correct
3 Correct 158 ms 7176 KB Output is correct

Subtask #5
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 9992 KB Output is correct
2 Correct 259 ms 9504 KB Output is correct
3 Correct 254 ms 9744 KB Output is correct

Subtask #6
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 287 ms 10344 KB Output is correct
2 Correct 233 ms 9776 KB Output is correct
3 Correct 283 ms 9744 KB Output is correct

Subtask #7
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 344 ms 11932 KB Output is correct
2 Correct 251 ms 10100 KB Output is correct
3 Correct 335 ms 12000 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 287 ms 9888 KB Output is correct
2 Correct 237 ms 10064 KB Output is correct
3 Correct 233 ms 10104 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 9864 KB Output is correct
2 Correct 203 ms 9924 KB Output is correct
3 Correct 191 ms 9724 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 9344 KB Output is correct
2 Correct 232 ms 10304 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 9936 KB Output is correct
2 Correct 347 ms 11416 KB Output is correct

Subtask #12
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 9668 KB Output is correct
2 Correct 294 ms 10212 KB Output is correct