이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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());
}
컴파일 시 표준 에러 (stderr) 메시지
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |