Submission #863978

#TimeUsernameProblemLanguageResultExecution timeMemory
863978wiiHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
100 / 100
646 ms76384 KiB
#include <bits/stdc++.h> using namespace std; typedef double db; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; #define X first #define Y second #define gcd __gcd #define pb push_back #define all(x) (x).begin(), (x).end() #define bit(i, mask) ((mask) >> (i) & 1) #define reset(x, val) memset(x, val, sizeof(x)) #define foru(i,a,b) for(int i = (a); i <= (b); ++i) #define ford(i,a,b) for(int i = (a); i >= (b); --i) #define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; } template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; } const ll Linf = 0x3f3f3f3f3f3f3f3f; const int Inf = 0x3f3f3f3f; const ll Mod = 1e9 + 7; const ll Mod2 = ll(1e9) + 9; const int Lim = 1e6 + 5; const int inv6 = 166666668; /// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*==== const int base = 3; const int N = 1e6 + 2; const int K = log2(N); const int dx[] = {+1, -1, 0, 0}; const int dy[] = {0, 0, +1, -1}; const int block_size = sqrt(2e9) + 2; using tup = tuple<int, int, int>; int n, q; int a[N]; int f[N]; vector<tup> qs[N]; void update(int u, int x) { for (; u > 0; u -= u & -u) maximize(f[u], x); } int get(int u) { int ans = 0; for (; u <= n; u += u & -u) maximize(ans, f[u]); return ans; } int ans[N]; void solve() { cin >> n >> q; foru(i, 1, n) cin >> a[i]; int l, r, k; foru(i, 1, q) { cin >> l >> r >> k; qs[r].emplace_back(l, k, i); } stack<int> st; foru(i, 1, n) { while (!st.empty() && a[i] >= a[st.top()]) st.pop(); if (!st.empty()) update(st.top(), a[i] + a[st.top()]);//, cout << i << " " << st.top() << " " << a[i] + a[st.top()] << "\n"; for (auto &[l, k, id]: qs[i]) { //cout << "? " << l << " " << i << " " << get(l) << "\n"; ans[id] = get(l) <= k; } st.push(i); } foru(i, 1, q) cout << ans[i] << "\n"; } signed main() { FastIO; #define task "test" if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } #ifdef Sieve Linear_sieve(); #endif #ifdef Ckn_calc precal_nck(); #endif int ntest = 1; // cin >> ntest; while (ntest--) { //cout << "Case " << q << ": " << "\n"; solve(); cout << "\n"; } return 0; } /** /\_/\ * (= ._.) * / >TL \>AC **/

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:91:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:92:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   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...