#include <bits/stdc++.h>
using namespace std;
const int N = 1000006, INF = 1000000009;
int n, qq;
int a[N];
vector<int> v[N * 4];
void bilv(int tl, int tr, int pos)
{
if (tl == tr)
{
v[pos].push_back(a[tl]);
return;
}
int m = (tl + tr) / 2;
bilv(tl, m, pos * 2);
bilv(m + 1, tr, pos * 2 + 1);
int j = 0;
for (int i = 0; i < v[pos * 2 + 1].size(); ++i)
{
while (j < v[pos * 2].size() && v[pos * 2][j] < v[pos * 2 + 1][i])
{
v[pos].push_back(v[pos * 2][j]);
++j;
}
v[pos].push_back(v[pos * 2 + 1][i]);
}
while (j < v[pos * 2].size())
{
v[pos].push_back(v[pos * 2][j]);
++j;
}
}
struct ban
{
int maxu;
int ans;
ban()
{
maxu = -INF;
ans = -INF;
}
ban(int x)
{
maxu = x;
ans = -INF;
}
};
ban t[N * 4];
ban mer(const ban& l, const ban& r, int pos)
{
ban res;
res.maxu = max(l.maxu, r.maxu);
res.ans = max(l.ans, r.ans);
int i = lower_bound(v[pos].begin(), v[pos].end(), l.maxu) - v[pos].begin();
--i;
if (i >= 0)
res.ans = max(res.ans, l.maxu + v[pos][i]);
return res;
}
void bil(int tl, int tr, int pos)
{
if (tl == tr)
{
t[pos] = ban(a[tl]);
return;
}
int m = (tl + tr) / 2;
bil(tl, m, pos * 2);
bil(m + 1, tr, pos * 2 + 1);
t[pos] = mer(t[pos * 2], t[pos * 2 + 1], pos * 2 + 1);
}
ban ans;
void qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return;
if (tl == l && tr == r)
{
ans = mer(ans, t[pos], pos);
return;
}
int m = (tl + tr) / 2;
qry(tl, m, l, min(m, r), pos * 2);
qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1);
}
int main()
{
freopen("input.txt", "r", stdin);
vector<int> v;
v.push_back(1);
cout << upper_bound(v.begin(), v.end(), 0) - v.begin() << endl;
return 0;
scanf("%d%d", &n, &qq);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
bilv(1, n, 1);
bil(1, n, 1);
while (qq--)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
ans = ban();
qry(1, n, l, r, 1);
if (ans.ans <= k)
printf("1\n");
else
printf("0\n");
}
return 0;
}
Compilation message
sortbooks.cpp: In function 'void bilv(int, int, int)':
sortbooks.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v[pos * 2 + 1].size(); ++i)
~~^~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < v[pos * 2].size() && v[pos * 2][j] < v[pos * 2 + 1][i])
~~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:29:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j < v[pos * 2].size())
~~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:96: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:101: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:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
sortbooks.cpp:109: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 |
116 ms |
125564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
125564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
125624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
125560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
125564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
125564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
