#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
using namespace std;
#define int long long
int log_ = 10;
int inf = 1000000000000000000;
int mod = 998244353;
struct segment_tree
{
vector <int> b;
vector <int> pr;
vector <int> mx;
vector <int> mx_pr;
vector <int> mn_pr;
int s = 1;
void init(int n)
{
while (s < n)
s *= 2;
b.resize(2 * s);
pr.resize(2 * s , -1);
mx.resize(2 * s);
mx_pr.resize(2 * s , -1);
mn_pr.resize(2 * s, -1);
}
void push(int ind)
{
if (pr[ind] == -1)
return;
pr[ind * 2 + 1] = pr[ind];
mx[ind * 2 + 1] = pr[ind * 2 + 1] + b[ind * 2 + 1];
mx_pr[ind * 2 + 1] = pr[ind];
pr[ind * 2 + 2] = pr[ind];
mx[ind * 2 + 2] = pr[ind * 2 + 2] + b[ind * 2 + 2];
mx_pr[ind * 2 + 2] = pr[ind];
mn_pr[ind * 2 + 1] = pr[ind];
mn_pr[ind * 2 + 2] = pr[ind];
pr[ind] = -1;
}
void build(int ind, int l, int r, vector <int>& a)
{
if (r - l == 1)
{
if (l < a.size())
{
b[ind] = a[l];
mx_pr[ind] = -1;
mn_pr[ind] = -1;
mx[ind] = 0;
}
return;
}
int m = (l + r) / 2;
build(ind * 2 + 1, l, m, a);
build(ind * 2 + 2, m, r, a);
b[ind] = max(b[ind * 2 + 1], b[ind * 2 + 2]);
mx[ind] = max(mx[ind * 2 + 1], mx[ind * 2 + 2]);
}
void build(vector <int>& a)
{
build(0, 0, s, a);
}
void modif(int ind, int l, int r, int rx, int x)
{
if (l >= rx)
return;
if (r > rx)
{
push(ind);
int m = (l + r) / 2;
modif(ind * 2 + 1, l, m, rx, x);
modif(ind * 2 + 2, m, r, rx, x);
mx[ind] = max(mx[ind * 2 + 1], mx[ind * 2 + 2]);
mx_pr[ind] = max(mx_pr[ind * 2 + 1], mx_pr[ind * 2 + 2]);
mn_pr[ind] = min(mn_pr[ind * 2 + 1], mn_pr[ind * 2 + 2]);
return;
}
if (mx_pr[ind] <= x)
{
pr[ind] = x;
mx[ind] = b[ind] + x;
mx_pr[ind] = x;
mn_pr[ind] = x;
return;
}
if (mn_pr[ind] > x)
{
return;
}
push(ind);
int m = (l + r) / 2;
modif(ind * 2 + 1, l, m, rx, x);
modif(ind * 2 + 2, m, r, rx, x);
mx[ind] = max(mx[ind * 2 + 1], mx[ind * 2 + 2]);
mx_pr[ind] = max(mx_pr[ind * 2 + 1], mx_pr[ind * 2 + 2]);
mn_pr[ind] = min(mn_pr[ind * 2 + 1], mn_pr[ind * 2 + 2]);
}
void modif(int rx, int x)
{
modif(0, 0, s, rx, x);
}
int get(int ind, int l, int r, int lx, int rx)
{
if ((lx <= l) and (r <= rx))
return mx[ind];
if ((rx <= l) or (r <= lx))
return 0;
push(ind);
int m = (l + r) / 2;
int g1 = get(ind * 2 + 1, l, m, lx, rx);
int g2 = get(ind * 2 + 2, m, r, lx, rx);
return max(g1, g2);
}
int get(int lx, int rx)
{
return get(0, 0, s, lx, rx);
}
};
signed main()
{
ios_base::sync_with_stdio();
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector <int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
segment_tree st;
st.init(n);
st.build(a);
vector < vector <pair <int, int>> > q(n);
vector <int> k(n);
for (int i = 0; i < m; i++)
{
int l, r;
cin >> l >> r >> k[i];
l--;
r--;
q[r].push_back({ l , i });
}
vector <int> ans(m);
stack <int> st_;
for (int i = 0; i < n; i++)
{
while ((st_.size() > 0) and (a[st_.top()] < a[i]))
st_.pop();
if (st_.size() != 0)
{
int ind = st_.top();
st.modif(ind + 1, a[i]);
}
for (int j = 0; j < q[i].size(); j++)
{
int l = q[i][j].first;
int ind = q[i][j].second;
ans[ind] = st.get(l, i + 1);
}
st_.push(i);
}
for (int i = 0; i < m; i++)
{
//cout << ans[i] << "\n";
if (ans[i] <= k[i])
cout << 1 << "\n";
else
cout << 0 << "\n";
}
}
Compilation message
sortbooks.cpp: In member function 'void segment_tree::build(long long int, long long int, long long int, std::vector<long long int>&)':
sortbooks.cpp:75:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | if (l < a.size())
| ~~^~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:246:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
246 | for (int j = 0; j < q[i].size(); j++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2340 ms |
181800 KB |
Output is correct |
| 2 |
Correct |
2359 ms |
190260 KB |
Output is correct |
| 3 |
Correct |
2343 ms |
190312 KB |
Output is correct |
| 4 |
Correct |
2374 ms |
190324 KB |
Output is correct |
| 5 |
Incorrect |
2223 ms |
190148 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
19996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
