제출 #690599

#제출 시각아이디문제언어결과실행 시간메모리
690599Nuraly_SerikbayHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
13 / 100
3043 ms26560 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]; void build (int v, int tl, int tr) { if (tl == tr) { if (tl == 1) return; if (a[tl] < a[tl - 1]) t[v] = 1; return; } int mid = (tl + tr) >> 1; build (v + v, tl, mid), build (v + v + 1, mid + 1, tr); t[v] = 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 (r < tl || tr < l) return 0; int mid = (tl + tr) >> 1; return get (v + v, tl, mid, l, r) + get (v + v + 1, mid + 1, tr, l, r); } void Solution () { cin >> n >> m; int mn = INF; for (int i = 1; i <= n; ++ i) { cin >> a[i]; mn = min (mn, a[i]); } set <int> s; int ok = 0; build (1, 1, n); for (int i = 1; i <= m; ++ i) { int l, r, k; cin >> l >> r >> k; if (k < mn) { if (get (1, 1, n, l + 1, r) > 0) cout << 0 << '\n'; else cout << 1 << '\n'; } else { ok = 0; s.clear(); for (int j = r; j >= l; -- j) { auto it = s.upper_bound (a[j]); if (it == s.begin()) { s.insert(a[j]); continue; } it --; if (*(it) + a[j] > k) { ok = 1; break; } s.insert (a[j]); } cout << (ok ? "0\n" : "1\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...