제출 #331116

#제출 시각아이디문제언어결과실행 시간메모리
331116FalconHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
867 ms195492 KiB
#pragma GCC optimize("O2") #include <bits/stdc++.h> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it) #define rep(i, N) for(int i = 0; i < (N); ++i) #define rrep(i, N) for(int i = (N) - 1; i >= 0; --i) #define rep1(i, N) for(int i = 1; i <= (N); ++i) #define rep2(i, s, e) for(int i = (s); i <= (e); ++i) #define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d)) #ifdef DEBUG #define debug(x...) { \ ++dbg::depth; \ string dbg_vals = dbg::to_string(x); \ --dbg::depth; \ dbg::fprint(__func__, __LINE__, #x, dbg_vals); \ } #define light_debug(x) { \ dbg::light = true; \ dbg::dout << __func__ << ":" << __LINE__; \ dbg::dout << " " << #x << " = " << x << endl; \ dbg::light = false; \ } #else #define debug(x...) 42 #define light_debug(x) 42 #endif using ll = long long; template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; } template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; } namespace segtree { struct node { int max_a{}, v{}, lzy{-1}; }; vector<node> seg; void push(int n, int s, int e) { if(seg[n].lzy == -1) return; seg[n].v = seg[n].max_a + seg[n].lzy; if(s != e) seg[n << 1].lzy = seg[n << 1 | 1].lzy = seg[n].lzy; seg[n << 1].lzy = -1; } void update(int n, int s, int e, int l, int r, int v) { push(n, s, e); if(r < s || e < l) return; if(l <= s && e <= r) { seg[n].lzy = v; push(n, s, e); return; } int m{(s + e) >> 1}; update(n << 1, s, m, l, r, v); update(n << 1 | 1, m + 1, e, l, r, v); seg[n].v = max(seg[n << 1].v, seg[n << 1 | 1].v); } void add_front(int n, int s, int e, int i, int v) { push(n, s, e); if(e < i || i < s) return; if(s == e) { assert(seg[n].max_a == 0 && seg[n].v == 0); seg[n].max_a = v; return; } int m{(s + e) >> 1}; add_front(n << 1, s, m, i, v), add_front(n << 1 | 1, m + 1, e, i, v); seg[n].v = max(seg[n << 1].v, seg[n << 1 | 1].v); seg[n].max_a = max(seg[n << 1].max_a, seg[n << 1 | 1].max_a); } int query(int n, int s, int e, int l, int r) { push(n, s, e); if(r < s || e < l) return 0; if(l <= s && e <= r) return seg[n].v; int m{(s + e) >> 1}; return max(query(n << 1, s, m, l, r), query(n << 1 | 1, m + 1, e, l, r)); } } // namespace segtree int main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef DEBUG freopen("debug", "w", stderr); #endif int N, M; cin >> N >> M; vector<int> A(N); segtree::seg.resize(N << 2); rep(i, N) cin >> A[i]; struct query { int i, r, k; }; vector<vector<query>> queries(N); vector<bool> ans(M); rep(i, M) { int l, r, k; cin >> l >> r >> k; --l, --r; queries[l].push_back({i, r, k}); } A.push_back(*max_element(all(A)) + 1); stack<int> max_vals; max_vals.push(N); rrep(i, N) { while(!max_vals.empty() && A[max_vals.top()] < A[i]) max_vals.pop(); int e = max_vals.top() - 1; debug(i, e); if(e > i) segtree::update(1, 0, N - 1, i + 1, e, A[i]); for(const query& q : queries[i]) { int x{segtree::query(1, 0, N - 1, i, q.r)}; debug(x, q.i); ans[q.i] = x <= q.k; } segtree::add_front(1, 0, N - 1, i, A[i]); max_vals.push(i); } for(const auto& b : ans) cout << b << '\n'; #ifdef DEBUG dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC << "ms" << endl; #endif return 0; }

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

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
sortbooks.cpp:145:9: note: in expansion of macro 'debug'
  145 |         debug(i, e);
      |         ^~~~~
sortbooks.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
sortbooks.cpp:149:13: note: in expansion of macro 'debug'
  149 |             debug(x, q.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...