Submission #479222

#	Time	Username	Problem	Language	Result	Execution time	Memory
479222		nafis_shifat	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	3074 ms	46916 KiB

sortbooks

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e6+5;
const int inf = 2e9 + 10;
int n, m;
int a[mxn] = {};

struct segtree {
    int tree[4*mxn];
    void build(int node,int b,int e) {
        if(b == e) {
            tree[node] = a[b];
            return;
        }
        int mid = b + e >> 1;
        int left = node << 1;
        int right = left | 1;
        build(left, b, mid);
        build(right, mid + 1, e);
        tree[node] = min(tree[left], tree[right]);
    }
    int query(int node,int b,int e,int l,int r) {
        if(e<l || b>r) return inf;
        if(b >= l && e <= r) return tree[node];
        int mid=b+e>>1;
        int left=node<<1;
        int right=left|1;
        return min(query(left, b, mid, l, r), query(right, mid + 1, e, l, r));
    }
} st;


struct BIT
{
    int bit[mxn] = {}; 

    void update(int p,int v) {
        if(p==0) return;
        for(;p<mxn;p+=p&-p) bit[p] += v;
    }
    int query(int p) {
        int r = 0;
        for(;p > 0; p -= p&-p) r += bit[p];
        return r;
    }

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
} bt, dn;
int main() {
    cin >> n >> m;
    vector<pii> b;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);

        b.emplace_back(a[i], i);
    }

    st.build(1, 1, n);

    vector< tuple<int, int, int, int> > query;

    for(int i = 1; i <= m; i++) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);

        int mn = st.query(1, 1, n, l, r);

        int v = k - mn;
        query.emplace_back(v, l, r, i);
    }

    sort(query.begin(), query.end(), greater<tuple<int, int, int, int> >());
    sort(b.begin(), b.end(), greater<pii>());

    int pt = 0;

    bool res[m + 1];



    for(auto [v, l, r, i] : query) {
        while(pt < n && b[pt].first > v) {
            auto [val, ind] = b[pt];
            pt++;
            if(a[ind] >= a[ind - 1]) bt.update(ind, 1);

            dn.update(ind, 1);
        }

        int tot = dn.query(l, r);

        if(tot == r - l + 1) res[i] = (bt.query(l + 1, r) == tot - 1);
        else {
            res[i] = true;
            for(int j = l; j < r; j++) {
                if(bt.query(j, j) == 1 && bt.query(j + 1, j + 1) == 0) {
                    res[i] = false;
                    break;
                }
            }
        }

    }

    for(int i = 1; i <= m; i++) {
        printf("%d\n", res[i]);
    }




}

Compilation message (stderr)

sortbooks.cpp: In member function 'void segtree::build(int, int, int)':
sortbooks.cpp:17:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         int mid = b + e >> 1;
      |                   ~~^~~
sortbooks.cpp: In member function 'int segtree::query(int, int, int, int, int)':
sortbooks.cpp:27:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int mid=b+e>>1;
      |                 ~^~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |     for(auto [v, l, r, i] : query) {
      |              ^
sortbooks.cpp:87:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |             auto [val, ind] = b[pt];
      |                  ^
sortbooks.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         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