oj.uz

Submission #397892

# Submission time Handle Problem Language Result Execution time Memory
397892 2021-05-03T10:55:22 Z ritul_kr_singh Temperature (POI11_tem) C++17
92 / 100
 535 ms 36688 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], k = n;

	vector<int> s;

	for(int i=0; i<n; ++i) cin >> l[i] >> r[i];

	SegmentTree st(n+1);
	
	for(int i=n-1; i>=0; --i){
		int j = min(n, st.firstGreater(-l[i]));
		st.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);	
}

Compilation message

tem.cpp: In function 'int main()':
tem.cpp:35:18: warning: unused variable 'k' [-Wunused-variable]
   35 |  int l[n], r[n], k = 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 204 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 5 ms 588 KB Output is correct
2 Correct 5 ms 624 KB Output is correct
3 Correct 5 ms 588 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 8784 KB Output is correct
2 Correct 212 ms 9272 KB Output is correct
3 Correct 240 ms 14220 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 16136 KB Output is correct
2 Correct 367 ms 15616 KB Output is correct
3 Correct 373 ms 26188 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 16620 KB Output is correct
2 Correct 377 ms 15892 KB Output is correct
3 Correct 445 ms 31376 KB Output is correct

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 16672 KB Output is correct
2 Correct 418 ms 15944 KB Output is correct
3 Runtime error 535 ms 36688 KB Memory limit exceeded

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 14804 KB Output is correct
2 Correct 372 ms 15944 KB Output is correct
3 Correct 394 ms 26588 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 15768 KB Output is correct
2 Correct 335 ms 16020 KB Output is correct
3 Correct 345 ms 15908 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 15300 KB Output is correct
2 Correct 339 ms 16036 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 16068 KB Output is correct
2 Correct 495 ms 16020 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 16024 KB Output is correct
2 Correct 481 ms 15180 KB Output is correct