제출 #534307

#제출 시각아이디문제언어결과실행 시간메모리
534307ac2hu무제 (POI11_tem)C++14
0 / 100
254 ms17652 KiB
#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); stack<int> st; for(int i =0;i<n;i++){ if(st.size() == 0) leftmost[i] = -1; else{ while(st.size() > 0 && rq.query(st.top(), i) <= a[i].second) st.pop(); if(st.size() == 0) leftmost[i] = -1; else leftmost[i] = st.top(); } st.push(i); } for(int i = 1;i<leftmost.size();i++) leftmost[i] = max(leftmost[i], leftmost[i - 1]); deb(leftmost); for(int i = 0;i<n;i++) leftmost[i] = i - leftmost[i]; deb(leftmost); cout << *max_element(leftmost.begin(),leftmost.end()); }

컴파일 시 표준 에러 (stderr) 메시지

tem.cpp: In function 'int main()':
tem.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 1;i<leftmost.size();i++)
      |                ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...