oj.uz

Submission #505881

# Submission time Handle Problem Language Result Execution time Memory
505881 2022-01-11T09:19:28 Z lukameladze Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 2259 ms 105084 KB 
# 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

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2248 ms 84480 KB Output is correct
2 Correct 2255 ms 88180 KB Output is correct
3 Correct 2259 ms 90496 KB Output is correct
4 Correct 2235 ms 89688 KB Output is correct
5 Incorrect 2017 ms 105084 KB Output isn't correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 8076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct