Submission #511475

#TimeUsernameProblemLanguageResultExecution timeMemory
511475Gev2706Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
17 / 100
2283 ms262144 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <string> #include <sstream> #include <iomanip> #include <map> #include <unordered_map> #include <stack> #include <cstdio> #include <climits> #include <tuple> #include <ctime> #include <cstring> #include <numeric> #include <functional> #include <chrono> #include <cassert> #include <bitset> using namespace std; using ll = long long; const int mod = 1e9 + 7; const int N = 5e6 + 5; #define full(a) a.begin(), a.end() #define eps 1e-9 int query(int l, int r, vector<vector<int>> &s) { int t = r - l + 1; t = log2(t); return min(s[l][t], s[r - (1 << t) + 1][t]); } void solve() { int n, m; cin >> n >> m; vector<int> w(n); for (int i = 0; i < n; i++)cin >> w[i]; if (n <= 5000 && m <= 5000) { while (m--) { int l, r, k; cin >> l >> r >> k; l--, r--; int ans = 1; set<int> s; s.insert(w[r]); for (int i = r - 1; i >= l; i--) { auto it = s.lower_bound(w[i]); if (it != s.begin()) { it--; if (*it + w[i] > k)ans = 0; } s.insert(w[i]); } cout << ans << endl; } } else { vector<int> v(n); stack<int> st; for (int i = 0; i < n; i++) { if (st.empty()) { st.push(i); continue; } while (!st.empty() && w[st.top()] > w[i]) { v[st.top()] = w[i]; st.pop(); } st.push(i); } while (!st.empty()) { v[st.top()] = -1; st.pop(); } vector<vector<int>> sp(n + 5, vector<int>(30, 0)); for (int i = 0; i < n; i++)sp[i][0] = v[i]; for (int i = 0; i < n; i++) { for (int j = 1; j + (1 << i) < n; j++) sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]); } while (m--) { int l, r; cin >> l >> r; l--, r--; cout << query(l, r, sp) << endl; } } } int main() { //int tc; cin >> tc;while(tc--) solve(); return 0; }
#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...