Submission #505887

#	Time	Username	Problem	Language	Result	Execution time	Memory
505887		lukameladze	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2630 ms	107164 KiB

sortbooks

# include <bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 1e6 + 5;
stack<int> st;
int n,q,a[N],le[N],ri[N],x[N];
vector <pii> v;
int tree[4*N],l,r,xx,curle,ans[N];
void update(int node, int le, int ri , int idx, int val) {
     if (le>idx || ri<idx) return ;
     if (le==ri) {
          tree[node]=max(tree[node],val);
          return;
     }
     int mid=(le+ri)/2;
     update(2*node , le, mid, idx, val);
     update(2*node+1, mid+1, ri, idx,val);
     tree[node]=max(tree[2*node], tree[2*node+1]);
}
int getans(int node, int le, int ri , int start, int end) {
     if (le>end || ri<start) return 0;
     if (le>=start && ri<=end) {
          return tree[node];
     }
     int mid=(le+ri)/2;
     return max(getans(2*node, le, mid ,start, end), getans(2*node+1, mid+1, ri , start, end));
}
void add(int idx) {
    int num = a[idx];
    while(st.size() && a[st.top()] < num) {
        int x = st.top();
        update(1,1,n,x,num + a[st.top()]);
        st.pop();
    }
    st.push(idx);
}
main() {
    cin>>n>>q;
    for (int i = 1; i <= n ;i++) {
        cin>>a[i];
    }
    for (int i = 1; i <= q; i++) {
        cin>>le[i]>>ri[i]>>x[i];
        v.pb({le[i],i});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    curle = n;
    for (int i = 0; i < v.size(); i++) {
        l = le[v[i].s];
        r = ri[v[i].s]; 
        xx = x[v[i].s]; 
        while (curle >= l) {
            add(curle);
            curle--;
        }
        ans[v[i].s] = (getans(1,1,n,l,r) <= xx);
    }
    for (int i = 1; i <= q; i++) {
        cout<<ans[i]<<" ";
    }
}

Compilation message (stderr)

sortbooks.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main() {
      | ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23