Submission #1116977

#TimeUsernameProblemLanguageResultExecution timeMemory
1116977JovicaHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
2852 ms54948 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=0;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> > pras; for (int i=0;i<q;i++) { int a,b,c; cin>>a>>b>>c; a--; b--; pras.push_back({b,a,c}); } sort(pras.begin(),pras.end()); int t = 0; for (int i=0;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])) cout<<1<<endl; else cout<<0<<endl; t++; //cout<< "x = "<<x<<endl; } } return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         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...