Submission #342598

#TimeUsernameProblemLanguageResultExecution timeMemory
342598OlerinskiyHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
1878 ms229532 KiB
#include <iostream> #include <iomanip> #include <algorithm> #include <bitset> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <cmath> #include <time.h> #include <random> #include <string> #include <cassert> #include <vector> #include <ostream> #include <istream> #include <stack> #include <deque> #include <queue> #include <functional> #include <chrono> #include <stack> using namespace std; // #define int long long #define pb push_back #define all(a) (a).begin(), (a).end() #define pii pair<int, int> #define ld long double istream& operator>> (istream& in, pii& b) { in >> b.first >> b.second; return in; } ostream& operator<< (ostream& out, const pii& b) { out << "{" << b.first << ", " << b.second << "}"; return out; } template<typename T> ostream& operator<< (ostream& out, const vector<T>& a) { for (auto k : a) out << k << " "; return out; } template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;} template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;} #ifdef LOCAL #define dbg(x) cout << #x << " : " << (x) << endl; const long long INF = 1e18; // const long long mod = 2600000069; // const long long p = 10; #else #define dbg(x) 57 const long long INF = 1e18; // const long long mod = 2600000069; // const long long p = 179; #endif const ld PI = 4 * atan(1); #define time clock() / (double) CLOCKS_PER_SEC // #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC target("sse,sse2,sse3,sse3,sse4") // #pragma GCC optimize("unroll-loops") // #pragma GCC optimize("fast-math") // #pragma GCC target("avx2") // #pragma GCC optimize("section-anchors") // #pragma GCC optimize("profile-values,profile-reorder-functions,tracer") // #pragma GCC optimize("vpt") // #pragma GCC optimize("rename-registers") // #pragma GCC optimize("move-loop-invariants") // #pragma GCC optimize("unswitch-loops") // #pragma GCC optimize("function-sections") // #pragma GCC optimize("data-sections") mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N = 1e6 + 10; int n, m; int a[N]; vector<int> t[4 * N]; void build(int v, int l, int r) { if (l + 1 == r) { t[v] = {a[l]}; return; } int m = (l + r) / 2; build(2 * v + 1, l, m); build(2 * v + 2, m, r); t[v].resize(r - l); merge(all(t[2 * v + 1]), all(t[2 * v + 2]), t[v].begin()); } vector<int> ind; void ask(int v, int l, int r, int askl, int askr) { if (l >= askr || r <= askl) return; if (l >= askl && r <= askr) { ind.pb(v); return; } int m = (l + r) / 2; ask(2 * v + 1, l, m, askl, askr); ask(2 * v + 2, m, r, askl, askr); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } build(0, 0, n); while (m--) { int l, r, k; cin >> l >> r >> k; ind.clear(); ask(0, 0, n, l - 1, r); int mx = 0; int ans = 1; for (auto v : ind) { int pos = upper_bound(all(t[v]), mx) - t[v].begin() - 1; if (pos >= 0 && t[v][pos] + mx > k) { ans = 0; break; } chkmax(mx, t[v].back()); } cout << ans << "\n"; } } /* */
#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...