제출 #254557

#제출 시각아이디문제언어결과실행 시간메모리
254557karmaHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
2728 ms104964 KiB
#include <bits/stdc++.h> #define pb emplace_back #define ll long long #define fi first #define se second #define mp make_pair //#define int int64_t using namespace std; const int N = int(1e6) + 7; typedef pair<int, int> pii; int a[N]; pii operator + (const pii& x, const pii& y) { if(x.fi <= y.se) return y; if(y.fi <= x.se) return x; return pii(max(x.fi, y.fi), min(x.fi, y.fi)); } struct TSegment { vector<int> l, h; vector<pii> st; TSegment() {} void init(int n) { l.resize(4 * n + 4); h.resize(l.size()); st.resize(l.size()); build(1, 1, n); } void build(int x, int low, int high) { l[x] = low, h[x] = high, st[x] = pii(0, 0); if(l[x] == h[x]) { st[x].fi = a[low]; return; } int mid = low + high >> 1; build(x << 1, low, mid); build(x << 1 | 1, mid + 1, high); } pii get(int x, int low, int high) { if(l[x] > high || h[x] < low) return pii(0, 0); if(low <= l[x] && h[x] <= high) return st[x]; return get(x << 1, low, high) + get(x << 1 | 1, low, high); } } it; int b[N], n, q; int get(int l, int r) { int low = l, high = r, mid; while(low <= high) { mid = low + high >> 1; if(b[r] - b[mid] == r - mid) high = mid - 1; else low = mid + 1; } /// from low to r is non-decreasing if(low == l) return 0; pii val = it.get(1, l, high); high = r; while(low <= high) { mid = low + high >> 1; if(a[mid] < val.fi) low = mid + 1; else high = mid - 1; } /// low to r no change val = it.get(1, l, high); return val.fi + val.se; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); #define Task "test" if(fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } cin >> n >> q; for(int i = 1; i <= n; ++i) { cin >> a[i]; b[i] = b[i - 1] + (a[i] >= a[i - 1]); } it.init(n); int l, r, k; while(q --) { cin >> l >> r >> k; if(get(l, r) <= k) cout << "1\n"; else cout << "0\n"; } }

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

sortbooks.cpp: In member function 'void TSegment::build(int, int, int)':
sortbooks.cpp:36:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = low + high >> 1;
                   ~~~~^~~~~~
sortbooks.cpp: In function 'int get(int, int)':
sortbooks.cpp:52:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         mid = low + high >> 1;
               ~~~~^~~~~~
sortbooks.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         mid = low + high >> 1;
               ~~~~^~~~~~
sortbooks.cpp: In function 'int32_t main()':
sortbooks.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...