제출 #172330

#제출 시각아이디문제언어결과실행 시간메모리
172330muradeynHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
737 ms80244 KiB
/* Murad Eynizade */ #include <bits/stdc++.h> #define intt long long #define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0); #define F first #define S second using namespace std; const int maxx = 1000005; int n , m; int we[maxx] , ans[maxx] , inv[maxx] , tree[maxx]; vector< int >st; vector< pair< pair<int,int> , pair<int,int> > >v; void update(int v,int l,int r,int in,int val) { if (l == r) { tree[v] = max(tree[v] , val); return; } int mid = (l + r) >> 1; if (in <= mid)update(v << 1,l,mid,in,val); else update(v << 1 | 1,mid + 1,r,in,val); tree[v] = max(tree[v << 1] , tree[v << 1 | 1]); } int get(int v,int l,int r,int le,int ri) { if (l > ri || r < le)return 0; if (l >= le && r <= ri)return tree[v]; int mid = (l + r) >> 1; return max(get(v << 1,l,mid,le,ri) , get(v << 1 | 1,mid + 1,r,le,ri)); } int main() { FAST_READ; cin>>n>>m; for (int i = 1;i<=n;i++)cin>>we[i]; for (int i = 1;i<=m;i++) { int l, r, k; cin>>l>>r>>k; v.push_back({{l , r} , {k , i}}); } sort(v.begin(),v.end()); for (int i = 1;i <= n;i++) { while (!st.empty() && we[st.back()] <= we[i])st.pop_back(); if (st.empty())inv[i] = -1; else inv[i] = st.back(); st.push_back(i); } for (int i = n;i >= 1;i--) { if (inv[i] != -1)update(1 , 1 , n , inv[i] , we[i] + we[inv[i]]); //cout<<i<<" "<<inv[i]<<endl; while (!v.empty() && v.back().F.F == i) { //cout<<v.back().F.F<<" "<<v.back().F.S<<endl; ans[v.back().S.S] = (get(1 , 1 , n , v.back().F.F , v.back().F.S) <= v.back().S.F); v.pop_back(); } } for (int i = 1;i<=m;i++)cout<<ans[i]<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...