oj.uz

답안 #397874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397874 2021-05-03T10:40:50 Z ritul_kr_singh Temperature (POI11_tem) C++17
50 / 100
 772 ms 44732 KB 
#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);	
}

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 2 ms 312 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 332 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 716 KB Output is correct
2 Correct 7 ms 716 KB Output is correct
3 Correct 10 ms 716 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 12272 KB Output is correct
2 Correct 337 ms 12704 KB Output is correct
3 Correct 398 ms 25228 KB Output is correct

Subtask #5
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 564 ms 22544 KB Output is correct
2 Runtime error 566 ms 34248 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 597 ms 22832 KB Output is correct
2 Runtime error 593 ms 34836 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 679 ms 23756 KB Output is correct
2 Runtime error 595 ms 35492 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 680 ms 23100 KB Output is correct
2 Runtime error 590 ms 33656 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 531 ms 23228 KB Output is correct
2 Correct 566 ms 28528 KB Output is correct
3 Correct 603 ms 28660 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 22844 KB Output is correct
2 Correct 599 ms 23516 KB Output is correct

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 591 ms 22496 KB Output is correct
2 Runtime error 772 ms 44732 KB Memory limit exceeded

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 590 ms 22256 KB Output is correct
2 Runtime error 669 ms 41756 KB Memory limit exceeded