이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
const int inf = 2e9;
const int maxn = 1e6 + 5;
struct query {
int l,r,k;
void read() {
cin>>l>>r>>k;
}
};
int n,q;
int t[maxn];
void upd(int v, int tl, int tr, int i, int val) {
if (tl==tr) {
t[v]=max(t[v],val);
} else {
int tm=(tl+tr)/2;
if (i<=tm) {
upd(2*v,tl,tm,i,val);
} else {
upd(2*v+1,tm+1,tr,i,val);
}
t[v]=max(t[2*v],t[2*v+1]);
}
}
int qry(int v, int tl, int tr, int l, int r) {
if (l>tr || r<tl) return -inf;
if (l<=tl && tr<=r) return t[v];
int tm=(tl+tr)/2;
return max(qry(2*v,tl,tm,l,r),qry(2*v+1,tm+1,tr,l,r));
}
int a[maxn];
query Q[maxn];
vector<int> ev[maxn];
int ans[maxn];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>q;
for (int i=1; i<=n; i++) {
cin>>a[i];
}
for (int i=1; i<=n; i++) {
Q[i].read();
ev[Q[i].r].push_back(i);
}
stack<int> stk;
vector<pair<int,int>> w;
for (int i=1; i<=n; i++) {
while (!stk.empty() && a[stk.top()]<=a[i]) stk.pop();
if (!stk.empty()) w.push_back({i,stk.top()});
stk.push(i);
}
sort(w.begin(),w.end());
int j=0;
for (int i=1; i<=n; i++) {
while (j<(int)w.size() && w[j].first<=i) {
upd(1,1,n,w[j].second, a[w[j].first]+a[w[j].second]);
++j;
}
for (int qi: ev[i]) {
if (qry(1,1,n,Q[qi].l,Q[qi].r)<=Q[qi].k) ans[qi]=1;
}
}
for (int i=1; i<=q; i++) {
cout<<ans[i]<<"\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |