Submission #690694

#TimeUsernameProblemLanguageResultExecution timeMemory
690694Nuraly_SerikbayHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
3031 ms8124 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]; set <int> pos[1005]; void build (int v, int tl, int tr) { if (tl == tr) { t[v] = a[tl]; return; } int mid = (tl + tr) >> 1; build (v + v, tl, mid), build (v + v + 1, mid + 1, tr); 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; 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) { for (int i = 1; i <= n; ++ i) pos[a[i]].insert (i); build (1, 1, n); for (int i = 1; i <= m; ++ i) { int l, r, k; cin >> l >> r >> k; if (k >= 2000) { cout << "1\n"; continue; } ok = 0; for (int i = 1; i <= mx; ++ i) { auto it = pos[i].upper_bound (r); if (it == pos[i].begin()) continue; it --; if (*(it) <= l) continue; int val = get (1, 1, n, l, *(it)); if (val > i && val + i > k) { // cout << ok = 1; break; } } cout << (ok ? "0\n" : "1\n"); } return; } /* set <int> s; build (1, 1, n); 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); }

Compilation message (stderr)

sortbooks.cpp:42:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   42 | const int INF = 1e18 + 7;
      |                 ~~~~~^~~
#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...