Submission #1345537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1345537		prince	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3094 ms	35584 KiB

sortbooks

    #include "bits/stdc++.h"

    using namespace std;

    struct segtree{
        vector<int> tree,ind;

        segtree(int n){
            tree.assign(n*4,0);
            ind.assign(n*4,0);
        }

        void build(int v,int l,int r,vector<int> &a){
            if(l == r){
                tree[v] = a[l-1];
                ind[v] = l;
            }else{
                int m = (l+r) >> 1;
                
                build(v*2,l,m,a);
                build(v*2+1,m+1,r,a);

                tree[v] = max(tree[v*2],tree[v*2+1]);

                if(tree[v] == tree[v*2])
                    ind[v] = ind[v*2];
                else ind[v] = ind[v*2+1];

            }
        }

        void update(int v,int l,int r,int i,int x){
            if(l == r){
                tree[v] = x;
            }else{
                int m = (l + r) >> 1;

                if(i<=m)
                    update(v*2,l,m,i,x);
                else 
                    update(v*2+1,m+1,r,i,x);

                tree[v] = max(tree[v*2],tree[v*2+1]);
                if(tree[v] == tree[v*2])
                    ind[v] = ind[v*2];
                else ind[v] = ind[v*2+1];
            }
        }

        pair<int,int> get(int v,int l,int r,int L,int R){
            if(L > R) return make_pair(-1e9,0);

            if(l == L && r == R) return make_pair(tree[v],ind[v]);

            int m = (l + r) >> 1;

            return max(get(v*2,l,m,L,min(m,R)),get(v*2+1,m+1,r,max(m+1,L),R));
        }
    };

    int main(){
        #ifdef whymagic
            freopen("input.txt","r",stdin);
            freopen("output.txt","w",stdout);
        #endif

        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        int n,m;
        cin >> n >> m;

        vector<int> a(n);

        for(auto &x : a)cin >> x;

        segtree sg(n);

        while(m--){
            sg.build(1,1,n,a);

            int l,r,w;
            cin >> l >> r >> w;

            int ok = 1;

            auto [x,i] = sg.get(1,1,n,l,r);

            while(x > 0){
                sg.update(1,1,n,i,0);
                auto [y,j] = sg.get(1,1,n,i+1,r);

                ok &= (x + y <= w);

                auto it = sg.get(1,1,n,l,r);

                x = it.first;
                i = it.second;
            }

            cout << ok << '\n';

        }

    }

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