#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
int v[1000005];
int ri[1000005];
int rez[1000005];
int aintm[4000005];
int aintr[4000005];
vector<int> a;
struct query
{
int st, dr;
int k, poz;
};
const int INF = 1e9 + 5;
void buildm(int nod, int st, int dr)
{
if(st == dr)
{
aintm[nod] = v[st];
return;
}
int mij = (st + dr) / 2;
buildm(nod * 2, st, mij);
buildm(nod * 2 + 1, mij + 1, dr);
aintm[nod] = min(aintm[nod * 2], aintm[nod * 2 + 1]);
}
int querym(int nod, int st, int dr, int le, int ri)
{
if(le > ri) return INF;
if(st == le && dr == ri)
return aintm[nod];
int mij = (st + dr) / 2;
return min(querym(nod * 2, st, mij, le, min(ri, mij)),
querym(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri));
}
void buildr(int nod, int st, int dr)
{
if(st == dr)
{
aintr[nod] = INF;
return;
}
int mij = (st + dr) / 2;
buildr(nod * 2, st, mij);
buildr(nod * 2 + 1, mij + 1, dr);
aintr[nod] = min(aintr[nod * 2], aintr[nod * 2 + 1]);
}
void updater(int nod, int st, int dr, int poz, int val)
{
if(st == dr)
{
aintr[nod] = val;
return;
}
int mij = (st + dr) / 2;
if(poz <= mij) updater(nod * 2, st, mij, poz, val);
else updater(nod * 2 + 1, mij + 1, dr, poz, val);
aintr[nod] = min(aintr[nod * 2], aintr[nod * 2 + 1]);
}
int queryr(int nod, int st, int dr, int le, int ri)
{
if(le > ri) return INF;
if(st == le && dr == ri)
return aintr[nod];
int mij = (st + dr) / 2;
return min(queryr(nod * 2, st, mij, le, min(ri, mij)),
queryr(nod * 2 + 1, mij + 1, dr, max(le, mij + 1), ri));
}
bool cmp(query a, query b)
{
return a.k > b.k;
}
bool cmp2(int a, int b)
{
return v[a] > v[b];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
stack<int> s;
int n, m;
cin>>n>>m;
map<int, int> mp1, mp2;
for(int i = 1; i <= n; i++)
cin>>v[i], mp1[v[i]] = 1;
int cnt = 0;
for(auto it : mp1)
mp2[it.first] = ++cnt;
for(int i = 1; i <= n; i++)
v[i] = mp2[v[i]];
for(int i = n; i >= 1; i--)
{
while(!s.empty() && v[i] <= v[s.top()])
s.pop();
if(s.empty()) ri[i] = n + 1;
else ri[i] = s.top();
s.push(i);
a.push_back(i);
}
buildm(1, 1, n);
buildr(1, 1, n);
vector<query> q;
for(int i = 1; i <= m; i++)
{
int st, dr, k, poz = i;
cin>>st>>dr>>k;
k -= querym(1, 1, n, st, dr);
q.push_back({st, dr, k, poz});
}
sort(q.begin(), q.end(), cmp);
sort(a.begin(), a.end(), cmp2);
int st = 0;
for(int i = 0; i < q.size(); i++)
{
while(st < n && v[a[st]] > q[i].k)
updater(1, 1, n, a[st], v[a[st]]), st++;
int val = queryr(1, 1, n, q[i].st, q[i].dr);
if(val > q[i].dr) rez[q[i].poz] = 1;
else rez[q[i].poz] = 0;
}
for(int i = 1; i <= m; i++)
cout<<rez[i]<<'\n';
return 0;
}
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:137:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i = 0; i < q.size(); i++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3021 ms |
156796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
18492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
