제출 #345293

#제출 시각아이디문제언어결과실행 시간메모리
345293RakhmandHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
64 / 100
3071 ms109920 KiB
// // A.cpp // torelax // // Created by Rakhman on 1/5/21. // #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <queue> #include <cmath> #include <cstdlib> #include <ctime> #include <cassert> #include <iterator> #define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0); #define S second #define F first #define pb push_back #define nl '\n' #define NL cout << '\n'; #define EX exit(0) #define all(s) s.begin(), s.end() #define no_answer {cout << "NO"; exit(0);} #define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k) const long long mxn = 1e6 + 110; const long long mnn = 1e3 + 2; const long long mod = 1e9 + 7; const long long inf = 1e18; const long long OO = 1e9 + 100; typedef long long llong; typedef unsigned long long ullong; using namespace std; int n, m, b[mxn], su[mxn], mx[mxn], pos[mxn]; int Q; vector<int> rightq[mxn]; struct query{ int l, r, x; }q[mxn]; void divideandconquer(int L, int R){ if(L == R) return ; int m = (L + R) / 2; vector<int> v; su[m + 1] = mx[m + 1] = 0; for(int i = m; i >= L; i--) { su[i] = max(su[i + 1], b[i]); mx[i] = mx[i + 1]; while(v.size() > 0 && v.back() <= b[i]){ if(b[i] > v.back()) mx[i] = max(mx[i], b[i] + v.back()); v.pop_back(); } v.push_back(b[i]); } int batkya = 0, mow = 0; vector<int> t; for(int i = m + 1; i <= R; i++){ if(t.size() == 0 || t.back() < b[i]){ t.push_back(b[i]); } if(batkya > b[i]) mow = max(mow, batkya + b[i]); batkya = max(batkya, b[i]); for(auto id : rightq[i]){ int left = q[id].l, k = q[id].x; if(!(L <= left && left <= m)){ continue; } if(pos[id] == 0 || max(mow, mx[left]) > k){ pos[id] = 0; continue; } int lol = lower_bound(t.begin(), t.end(), su[left]) - t.begin() - 1; if(0 <= lol && lol < t.size()){ if(t[lol] + su[left] > k){ pos[id] = 0; continue; } } } } divideandconquer(L, m); divideandconquer(m + 1, R); } int main() { cin >> n >> Q; for(int i = 1; i <= n; i++){ cin >> b[i]; } for(int i = 1; i <= Q; i++){ cin >> q[i].l >> q[i].r >> q[i].x; rightq[q[i].r].push_back(i); pos[i] = 1; } divideandconquer(1, n); for(int i = 1; i <= Q; i++){ cout << pos[i] << nl; } }

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

sortbooks.cpp: In function 'void divideandconquer(int, int)':
sortbooks.cpp:94:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             if(0 <= lol && lol < t.size()){
      |                            ~~~~^~~~~~~~~~
#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...