#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
//#include <bit>
//#include <ranges>
//#include <numbers>
#define itn int
#define sacnf scanf
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 1e6 + 5;
int fm(int& L, int& R, vector<int>& l, vector<vector<int>>& st)
{
int j = l[R - L + 1];
return min(st[L][j], st[R - (1 << j) + 1][j]);
}
int fmx(int& L, int& R, vector<int>& l, vector<vector<int>>& st)
{
int j = l[R - L + 1];
return max(st[L][j], st[R - (1 << j) + 1][j]);
}
int main()
{
/*ios_base::sync_with_stdio(false);
cin.tie(NULL);*/
int n, m;
scanf("%d%d", &n, &m);
vector<int> v(n);
bool flag = 1;
for (int i = 0; i < n; i++)
{
scanf("%d", &v[i]);
if (v[i] > 1000)
{
flag = 0;
break;
}
}
if (n <= 5000 && m <= 5000)
{
for (int i = 0; i < m; i++)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
l--, r--;
int mx_num = 0, mx = 0;
for (int j = l; j <= r; j++)
{
if (mx_num > v[j]) mx = max(mx, v[j] + mx_num);
mx_num = max(mx_num, v[j]);
}
if (mx <= k) printf("1\n");
else printf("0\n");
}
}
if (flag)
{
// subtask 4
vector<vector<int>> id(1001);
for (int i = 0; i < n; i++) id[v[i]].push_back(i);
vector<vector<int>> st(n + 2, vector<int>(22));
for (int i = 0; i < n; i++) st[i][0] = v[i];
for (int j = 1; j <= 21; j++)
for (int i = 0; i + (1 << j) < n + 2; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
vector<int> g(n + 2);
g[1] = 0;
for (int i = 2; i < n + 2; i++)
g[i] = g[i / 2] + 1;
while (m--)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
if (k >= 2000) printf("1\n");
else
{
l--, r--;
for (int num = 0; num <= 1000; num++)
{
auto it = upper_bound(id[num].begin(), id[num].end(), r);
if (id[num].empty() || it == id[num].begin()) continue;
it--;
int index = *it;
index--;
if (index < l) continue;
if (fmx(l, index, g, st) + num > k)
{
flag = 0;
break;
}
}
if (flag) printf("1\n");
else printf("0\n");
}
}
}
else
{
// subtask 3
stack<int> s;
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
int next = v[i];
if (s.empty())
{
s.push(i);
continue;
}
while (!s.empty() && v[s.top()] > next)
{
ans[s.top()] = i;
s.pop();
}
s.push(i);
}
while (!s.empty())
{
ans[s.top()] = 2e9;
s.pop();
}
vector<vector<int>> st(n + 2, vector<int>(22));
for (int i = 0; i < n; i++) st[i][0] = ans[i];
for (int j = 1; j <= 21; j++)
for (int i = 0; i + (1 << j) < n + 2; i++)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
vector<int> g(n + 2);
g[1] = 0;
for (int i = 2; i < n + 2; i++)
g[i] = g[i / 2] + 1;
while (m--)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
l--, r--;
if (fm(l, r, g, st) <= r) printf("0\n");
else printf("1\n");
}
}
return 0;
}
// https://codeforces.com/problemset/problem/1136/D?locale=ru
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d", &v[i]);
| ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d%d", &l, &r, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d%d%d", &l, &r, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:162:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
162 | scanf("%d%d%d", &l, &r, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
387 ms |
262144 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1356 ms |
13540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
