oj.uz

Submission #978889

# Submission time Handle Problem Language Result Execution time Memory
978889 2024-05-10T00:33:07 Z Sofiatpc Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1516 ms 82368 KB 
#include <bits/stdc++.h>

using namespace std;

struct query{
    int r,k,id;
};
#define sz(v) (int)v.size()
const int MAXN = 1e6+5;
int w[MAXN], r[MAXN], ans[MAXN], mx[MAXN*4], mxs[MAXN*4];
vector<int> st;
vector<query> q[MAXN];
query temp; 

void build(int node, int l, int r){
    mxs[node] = -1;
    if(l==r){
        mx[node] = w[l];
        return;
    }

    int mid = (l+r)>>1, e = node*2, d = node*2+1;
    build(e,l,mid); build(d,mid+1,r);
    mx[node] = max(mx[e],mx[d]);
}

int query(int node, int l, int r, int i, int j){
    if(j < l || r < i)return -1;
    if(i <= l && r <= j)return mx[node];
    int mid = (l+r)>>1, e = node*2, d = node*2+1;
    return max(query(e,l,mid,i,j),query(d,mid+1,r,i,j));
}

void updateS(int node, int l, int r, int i, int x){
    if(i < l || r < i)return;
    if(l==r){
        mxs[node] = x;
        return;
    }

    int mid = (l+r)>>1, e = node*2, d = node*2+1;
    updateS(e,l,mid,i,x); updateS(d,mid+1,r,i,x);
    mxs[node] = max(mxs[e],mxs[d]);
}

int queryS(int node, int l, int r, int i, int j){
    if(j < l || r < i)return -1;
    if(i <= l && r <= j)return mxs[node];
    int mid = (l+r)>>1, e = node*2, d = node*2+1;
    return max(queryS(e,l,mid,i,j),queryS(d,mid+1,r,i,j));
}

int bb( int x){
    int l = 0, r = sz(st)-1;
    while(l!=r){
        int mid = (l+r)/2;
        if(st[mid] <= x)r = mid;
        else l = mid+1;
    }
    return st[l];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n,m; cin>>n>>m;
    for(int i = 1; i <= n; i++)cin>>w[i];
    build(1,1,n);

    for(int i = 1; i <= m; i++){
        int l;
        cin>>l>>temp.r>>temp.k;
        temp.id = i;
        q[l].push_back(temp);
    }

    for(int i = n; i >= 1; i--){
        int mx = -1;
        while(sz(st) > 0 && w[st.back()] <= w[i]){
            updateS(1,1,n,st.back(),0);
            mx = w[st.back()];
            st.pop_back();
        }
        if(mx >= 0)updateS(1,1,n,i,w[i]+mx);
        st.push_back(i);

        for(int j = 0; j < sz(q[i]); j++){
            //for(int z : st)cout<<z<<" "<<w[z]<<", "; cout<<"\n";
            int u = bb(q[i][j].r); 
            int a = queryS(1,1,n,i,u-1), b = query(1,1,n,u+1,q[i][j].r);
            //cout<<u<<" "<<a<<" "<<b<<"\n";
            if(b >= 0)b += w[u];

            ans[q[i][j].id] = ( max(a,b) <= q[i][j].k );
        }
    }

    for(int i = 1; i <= m; i++)cout<<ans[i]<<"\n";
    
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 7 ms 31436 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 8 ms 31324 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Incorrect 7 ms 31576 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 7 ms 31436 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 8 ms 31324 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Incorrect 7 ms 31576 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1434 ms 78388 KB Output is correct
2 Correct 1456 ms 78172 KB Output is correct
3 Correct 1516 ms 78172 KB Output is correct
4 Correct 1506 ms 78256 KB Output is correct
5 Incorrect 1431 ms 82368 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 7 ms 31436 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 8 ms 31324 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Incorrect 7 ms 31576 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 7 ms 31436 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 8 ms 31324 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Incorrect 7 ms 31576 KB Output isn't correct
11 Halted 0 ms 0 KB -