Submission #536478

#	Time	Username	Problem	Language	Result	Execution time	Memory
536478		PiejanVDC	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	1276 ms	102828 KiB

sortbooks

#include<bits/stdc++.h>

std::vector<bool>st;
std::vector<std::pair<int,int>>v;
std::vector<int>w;

void build(int i, int j, int p) {
    if(i == j) {
        st[p] = 1;
        v[p] = {w[i],w[i]};
        return;
    }
    int mid = (i+j) >> 1;
    build(i,mid,2*p);
    build(mid+1,j,2*p+1);
    if(!st[2*p] || !st[2*p+1]) {
        st[p] = 0; return;
    }
    if(v[2*p].first > v[2*p+1].second) st[p] = 0;
    else st[p] = 1;
    v[p].first = v[2*p+1].first, v[p].second = v[2*p].second;
}

int l,r, ans;

std::pair<int,int> query(int i, int j, int p) {
    if(i > r || j < l) return {-1,-1};
    if(i >= l && j <= r) {
        if(!st[p]) ans = 0;
        return v[p];
    }
    int mid = (i+j) >> 1;
    auto x = query(i,mid,2*p), y = query(mid+1,j,2*p+1);
    if(!ans) return {-1,-1};
    if(x.first == -1)
        return y;
    if(y.first == -1)
        return x;
    if(x.first > y.second) {
        ans = 0;
        return {-1,-1};
    }
    x.first = y.first;
    return x;
}

int k;

signed main() {
    int n,q; scanf("%d%d",&n,&q);
    v.resize(8 * n);
    st.resize(8 * n);
    w.resize(n);
    for(auto &z : w)
        scanf("%d", &z);
    build(0,n-1,1);
    while(q--) {
        scanf("%d%d%d", &l, &r, &k);
        ans = 1;
        l--,r--;
        query(0,n-1,1);
        printf("%d\n", ans);
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:50:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     int n,q; scanf("%d%d",&n,&q);
      |              ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d", &z);
      |         ~~~~~^~~~~~~~~~
sortbooks.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d%d%d", &l, &r, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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