# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
534314 |
2022-03-08T04:22:23 Z |
ac2hu |
Temperature (POI11_tem) |
C++14 |
|
1000 ms |
17644 KB |
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else
#define deb(x...)
#endif
using namespace std;
template<class T> struct Seg { // comb(ID,b) = b
const T ID = -1e9; T comb(T a, T b) { return max(a,b); }
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n,ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // min on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
signed main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int n;cin >> n;
vector<pair<int,int>> a(n);
for(auto &e : a)cin >> e.first >> e.second;
Seg<int> rq;
rq.init(n);
for(int i = 0;i<n;i++){
rq.upd(i,a[i].first);
}
vector<int> leftmost(n);
for(int i =0;i<n;i++){
int l = 0,r = i;
while(l < r){
int mid = (l + r)/2;
if(rq.query(mid,i) <= a[i].second)
r = mid;
else
l = mid + 1;
}
leftmost[i] = l;
}
for(int i = 1;i<leftmost.size();i++)
leftmost[i] = max(leftmost[i], leftmost[i - 1]);
for(int i = 0;i<n;i++)
leftmost[i] = i - leftmost[i] + 1;
deb(leftmost);
cout << *max_element(leftmost.begin(),leftmost.end());
}
Compilation message
tem.cpp: In function 'int main()':
tem.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 1;i<leftmost.size();i++)
| ~^~~~~~~~~~~~~~~~
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
460 KB |
Output is correct |
2 |
Correct |
14 ms |
460 KB |
Output is correct |
3 |
Correct |
16 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
830 ms |
9276 KB |
Output is correct |
2 |
Correct |
904 ms |
10536 KB |
Output is correct |
3 |
Execution timed out |
1055 ms |
11928 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1081 ms |
14404 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1079 ms |
15208 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1067 ms |
17644 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1061 ms |
16132 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1084 ms |
16120 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1089 ms |
15176 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1096 ms |
14276 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1079 ms |
13752 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |