제출 #690717

#제출 시각아이디문제언어결과실행 시간메모리
690717Nuraly_SerikbayHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
13 / 100
846 ms46984 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], pref[N], res[N], l[N], r[N], k[N]; int pos[1005], sp[N][20], lg[N]; vector <int> qu[N]; int get (int l, int r) { int val = lg [r - l + 1]; return max (sp[l][val], sp[r - (1 << (val)) + 1][val]); } void Solution () { cin >> n >> m; int mn = INF, mx = 0; for (int i = 1; i <= n; ++ i) { cin >> a[i]; mx = max (mx, a[i]); mn = min (mn, a[i]); pref[i] = pref[i - 1]; if (i > 1 && a[i] < a[i - 1]) pref[i] ++; } int ok = 0; if (mx <= 1000) { sp[1][0] = a[1]; for (int i = 2; i <= n; ++ i) sp[i][0] = a[i], lg[i] = lg[i / 2] + 1; for (int pw = 1; pw <= lg[n]; ++ pw) { for (int i = 1; i + (1 << (pw)) - 1 <= n; ++ i) { sp[i][pw] = max (sp[i][pw - 1], sp[i + (1 << (pw - 1))][pw - 1]); } } for (int i = 1; i <= m; ++ i) { cin >> l[i] >> r[i] >> k[i]; qu[r[i]].pb (i); } for (int i = 1; i <= n; ++ i) { pos[a[i]] = i; for (auto to: qu[i]) { ok = 0; for (int j = 1; j <= 1000; ++ j) { if (get (l[to], pos[j]) > j && get (l[to], pos[j]) + j > k[to]) { ok = 1; break; } } res[to] = 1 - ok; } } for (int i = 1; i <= m; ++ i) cout << res[i] << '\n'; return; } set <int> s; for (int i = 1; i <= m; ++ i) { int l, r, k; cin >> l >> r >> k; if (k < mn) { if (pref[r] - pref[l] > 0) cout << 0 << '\n'; else cout << 1 << '\n'; } else { ok = 0; s.clear(); for (int j = r; j >= l; -- j) { auto it = s.lower_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...