Submission #1117126

#TimeUsernameProblemLanguageResultExecution timeMemory
1117126JovicaHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
100 / 100
2891 ms86220 KiB
#include <bits/stdc++.h> using namespace std; int pogolem[1000000]; int niza[1000000]; int drvo[2500000]; int p; int update(int l,int r,int poz,int k) { if (p<l || r<p) return drvo[poz]; if (l==r) { drvo[poz] = max(drvo[poz],k); return drvo[poz]; } int mid = (l+r)/2; drvo[poz] = max(update(l,mid,poz*2,k),update(mid+1,r,poz*2+1,k)); return drvo[poz]; } int najdi(int l,int r,int poz,int levo,int desno) { if (levo<=l && r<=desno) return drvo[poz]; if (r<levo || desno<l) return 0; int mid = (l+r)/2; return max(najdi(l,mid,poz*2,levo,desno),najdi(mid+1,r,poz*2+1,levo,desno)); } int main() { int n,q; cin>>n>>q; int ns = 1; while (ns<n) ns*=2; stack<int> s; for (int i=1;i<=n;i++) { int a; cin>>a; niza[i] = a; while(s.size() && niza[s.top()]<=a) s.pop(); if (s.size()) pogolem[i] = s.top(); else pogolem[i] = -1; s.push(i); } /* cout<<"pogolem: "; for (int i=0;i<n;i++) cout<<pogolem[i]<<" "; cout<<endl; */ vector<tuple<int,int,int,int> > pras; for (int i=0;i<q;i++) { int a,b,c; cin>>a>>b>>c; pras.push_back({b,a,c,i}); } sort(pras.begin(),pras.end()); int t = 0; vector<pair<int,int> > odg; for (int i=1;i<=n;i++) { if (pogolem[i]!=-1) { p = pogolem[i]; update(1,ns,1,niza[i]+niza[p]); } while(t<pras.size() && get<0>(pras[t])==i) { int x = najdi(1,ns,1, get<1>(pras[t]),get<0>(pras[t])); if (x<=get<2>(pras[t])) odg.push_back({get<3>(pras[t]),1}); else odg.push_back({get<3>(pras[t]),0}); //cout<<"l = "<<get<1>(pras[t])<<" r = "<<get<0>(pras[t])<< " x = "<<x<<endl; t++; } } sort(odg.begin(),odg.end()); for (auto a : odg) cout<<a.second<<endl; return 0; } /* 5 15 2 7 6 8 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 2 2 2 2 3 2 2 4 2 2 5 2 3 3 3 3 4 3 3 5 3 4 4 4 4 5 4 5 5 5 */

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         while(t<pras.size() && get<0>(pras[t])==i)
      |               ~^~~~~~~~~~~~
#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...