#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 1000006, INF = 1000000009;
int n, qq;
int a[N];
vector<pair<pair<int, int>, int> > v[N];
int t[N * 4];
int laz[N * 4];
void shi(int pos)
{
if (laz[pos] == 0)
return;
t[pos * 2] = max(t[pos * 2], laz[pos]);
laz[pos * 2] = max(laz[pos * 2], laz[pos]);
t[pos * 2 + 1] = max(t[pos * 2 + 1], laz[pos]);
laz[pos * 2 + 1] = max(laz[pos * 2 + 1], laz[pos]);
laz[pos] = 0;
}
void ubd(int tl, int tr, int l, int r, int y, int pos)
{
if (l > r)
return;
if (tl == l && tr == r)
{
t[pos] = max(t[pos], y);
laz[pos] = max(laz[pos], y);
return;
}
shi(pos);
int m = (tl + tr) / 2;
ubd(tl, m, l, min(m, r), y, pos * 2);
ubd(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}
int qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return 0;
if (tl == l && tr == r)
return t[pos];
shi(pos);
int m = (tl + tr) / 2;
return max(qry(tl, m, l, min(m, r), pos * 2),
qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
char ans[N];
int main()
{
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &qq);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= qq; ++i)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
v[r].push_back(m_p(m_p(l, k), i));
}
stack<int> s;
for (int i = 1; i <= n; ++i)
{
while (!s.empty() && a[i] >= a[s.top()])
s.pop();
if (!s.empty())
{
ubd(1, n, 1, s.top(), a[i] + a[s.top()], 1);
}
s.push(i);
for (int j = 0; j < v[i].size(); ++j)
{
if (qry(1, n, v[i][j].first.first, i, 1) <= v[i][j].first.second)
ans[v[i][j].second] = '1';
else
ans[v[i][j].second] = '0';
}
}
for (int i = 1; i <= qq; ++i)
printf("%c\n", ans[i]);
return 0;
}
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:77:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); ++j)
~~^~~~~~~~~~~~~
sortbooks.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &qq);
~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
sortbooks.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &l, &r, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
