제출 #690830

#제출 시각아이디문제언어결과실행 시간메모리
690830Nuraly_SerikbayHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
1332 ms84864 KiB
/* Speech to the young */ //#include <bits/stdc++.h> #include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <string> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <fstream> #include <numeric> #include <sstream> #include <cassert> #include <iomanip> #include <iostream> #include <algorithm> #include <stdio.h> #include <fstream> #include <unordered_map> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define F first #define S second #define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0) #define int long long #define pans cout << "\n------ans-------\n" const int N = 1e6 + 10; const int INF = 1e18 + 7; const int MOD = 1e9 + 7; const int P = 31; int n, m, t[N * 4]; int a[N], res[N], l[N], r[N], k[N]; vector <int> qu[N]; void upd (int v, int tl, int tr, int pos, int val) { if (tl == tr) { t[v] = max (t[v], val); return; } int mid = (tl + tr) >> 1; if (mid <= pos) upd (v + v, tl, mid, pos, val); else upd (v + v + 1, mid + 1, tr, pos, val); t[v] = max (t[v + v], t[v + v + 1]); return; } int get (int v, int tl, int tr, int l, int r) { if (l <= tl && tr <= r) return t[v]; if (tr < l || r < tl) return 0; int mid = (tl + tr) >> 1; return max (get (v + v, tl, mid, l, r), get (v + v + 1, mid + 1, tr, l, r)); } void Solution () { cin >> n >> m; for (int i = 1; i <= n; ++ i) cin >> a[i]; stack <int> s; for (int i = 1; i <= m; ++ i) { cin >> l[i] >> r[i] >> k[i]; qu[r[i]].pb (i); } s.push (0); a[0] = INF; for (int i = 1; i <= n; ++ i) { while (a[s.top()] <= a[i]) s.pop(); if (s.top() != 0) upd (1, 1, n, s.top(), a[s.top()] + a[i]); s.push (i); for (auto to: qu[i]) if (get (1, 1, n, l[to], i) <= k[to]) res[to] = 1; } for (int i = 1; i <= m; ++ i) cout << res[i] << '\n'; return; } signed main () { YOSIK(); // precalc(); int T = 1; //cin >> T; while (T --) Solution (); exit (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...