Submission #371082

#TimeUsernameProblemLanguageResultExecution timeMemory
371082nicolaalexandraHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
34 / 100
295 ms8812 KiB
#include <bits/stdc++.h> #define DIM 100010 using namespace std; struct query{ int x,val,poz; }; vector <query> qry[DIM]; int v[DIM],aint[DIM*4],ans[DIM]; deque <int> d; int n,m,i,sol,x,y,val; void update (int nod, int st, int dr, int poz, int val){ if (st == dr){ aint[nod] = max (aint[nod],val); return; } int mid = (st+dr)>>1; if (poz <= mid) update (nod<<1,st,mid,poz,val); else update ((nod<<1)|1,mid+1,dr,poz,val); aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]); } void query (int nod, int st, int dr, int x, int y){ if (x <= st && dr <= y){ sol = max (sol,aint[nod]); return; } int mid = (st+dr)>>1; if (x <= mid) query (nod<<1,st,mid,x,y); if (y > mid) query ((nod<<1)|1,mid+1,dr,x,y); } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>m; for (i=1;i<=n;i++) cin>>v[i]; for (i=1;i<=m;i++){ cin>>x>>y>>val; qry[y].push_back({x,val,i}); ans[i] = 1; } for (i=1;i<=n;i++){ while (!d.empty() && v[i] >= v[d.back()]) d.pop_back(); if (!d.empty()) update (1,1,n,d.back(),v[i] + v[d.back()]); d.push_back(i); for (auto it : qry[i]){ sol = 0; query (1,1,n,it.x,i); if (sol > it.val) ans[it.poz] = 0; } } for (i=1;i<=m;i++) cout<<ans[i]<<"\n"; return 0; }
#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...