Submission #377234

#	Time	Username	Problem	Language	Result	Execution time	Memory
377234		ntabc05101	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	34 / 100	821 ms	128748 KiB

sortbooks

#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>

#define taskname ""

#define f first
#define s second

const int max_n=100000;

int nodes[max_n<<2];
int L[max_n<<2], H[max_n<<2];

void buildRange(int node, int low, int high) {
        L[node]=low, H[node]=high;
        if (low==high) {
                return ;
        }

        int mid=low+high>>1;
        buildRange(node<<1, low, mid);
        buildRange(node<<1|1, mid+1, high);
}

void update(int node, int posq, int value) {
        if (L[node]==H[node]) {
                nodes[node]=std::max(nodes[node], value);
                return ;
        }

        if (posq>H[node<<1]) {
                update(node<<1|1, posq, value);
        }
        else {
                update(node<<1, posq, value);
        }

        nodes[node]=std::max(nodes[node<<1], nodes[node<<1|1]);
}

int get(int node, int leftq, int rightq) {
        if (leftq>H[node] or rightq<L[node]) {
                return 0;
        }

        if (leftq<=L[node] and rightq>=H[node]) {
                return nodes[node];
        }

        return std::max(get(node<<1, leftq, rightq), get(node<<1|1, leftq, rightq));
}

int main() {
        if (fopen(taskname".inp", "r")) {
                freopen(taskname".inp", "r", stdin);
                freopen(taskname".out", "w", stdout);
        }
        else if (fopen(taskname".in", "r")) {
                freopen(taskname".in", "r", stdin);
                freopen(taskname".out", "w", stdout);
        }

        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int n, m; std::cin>>n>>m;
        int w[n];
        for (int i=0; i<n; ++i) {
                std::cin>>w[i];
        }

        std::vector< std::pair< std::pair<int, int>, int > > q[n];
        for (int i=0; i<m; ++i) {
                int left, right, k; std::cin>>left>>right>>k;

                --left, --right;
                q[right].push_back({{left, k}, i});
        }

        bool result[m];
        buildRange(1, 0, n-1);
        std::deque<int> deq;
        for (int i=0; i<n; ++i) {
                while (!deq.empty() and w[deq.back()]<=w[i]) {
                        deq.pop_back();
                }

                if (!deq.empty()) {
                        update(1, deq.back(), w[deq.back()]+w[i]);
                }
                deq.push_back(i);

                for (auto& Q: q[i]) {
                        result[Q.s]=(get(1, Q.f.f, i)<=Q.f.s);
                }
        }

        for (int i=0; i<m; ++i) {
                std::cout<<result[i]<<"\n";
        }

        return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void buildRange(int, int, int)':
sortbooks.cpp:22:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid=low+high>>1;
      |                 ~~~^~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:57:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   57 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:58:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   58 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   61 |                 freopen(taskname".in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:62:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   62 |                 freopen(taskname".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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