Submission #286338

#	Time	Username	Problem	Language	Result	Execution time	Memory
286338		SomeoneUnknown	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	2487 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
vector<int> bks;

struct node{
    int lo, hi, mid, heaviestswap;
    vector<int> svals;
    node *lft, *rght;

    node(int l, int h){
        lo = l;
        hi = h;
        mid = (l+h)/2;
        if(l == h){
            heaviestswap = 0;
            svals.push_back(bks[l]);
        }else{
            lft = new node(l, mid);
            rght = new node(mid+1, h);
            heaviestswap = max(lft->heaviestswap, rght->heaviestswap);
            bool hstbd = true;
            int lmax = lft->svals.back();
            if(lmax > rght->svals.back()){
                hstbd = false;
                heaviestswap = max(heaviestswap, lft->svals.back()+rght->svals.back());
            }//*/
            int lp = 0;
            int rp = 0;
            lft->svals.push_back(1000000009);
            rght->svals.push_back(1000000009);
            while(lp < lft->svals.size()-1 || rp < rght->svals.size()-1){
                if(hstbd && rght->svals[rp] >= lmax){
                    hstbd = false;
                    if(rp != 0){
                        heaviestswap = max(heaviestswap, lmax+rght->svals[rp-1]);
                    }
                }
                if(lft->svals[lp] > rght->svals[rp]){
                    svals.push_back(rght->svals[rp]);
                    ++rp;
                }else{
                    svals.push_back(lft->svals[lp]);
                    ++lp;
                }
            }
            lft->svals.pop_back();
            rght->svals.pop_back();
        }
    }

    int ghs(int l, int h){ //Get heaviest swap
        if(l <= lo && hi <= h){
            return heaviestswap;
        }
        //int rmin = mex;
        int lmax = -1000000009;
        int res = 0;
        if(l <= mid){
            res = max(res, lft->ghs(l,h));
            lmax = lft->glnstx(l,h,1000000009);
        }
        if(mid < h){
            res = max(res, rght->ghs(l,h));
            res = max(res, lmax+rght->glnstx(l,h,lmax));
        }
        return res;
    }

    int glnstx(int l, int h, int x){ //get largest number smaller than x
        if(l <= lo && hi <= h){
            if(x == 1000000009) return svals.back();
            int l1 = -1;
            int h1 = svals.size();
            while(h1-l1 > 1){
                int m1 = (h1+l1)/2;
                if(svals[m1] < x){
                    l1 = m1;
                }else{
                    h1 = m1;
                }
            }
            if(l1 == -1) return -1000000009;
            return svals[l1];
        }
        //int rmin = mex;
        int best = -1000000009;
        if(mid < h){
            best = max(best, rght->glnstx(l, h, x));
        }
        if(l <= mid){
            best = max(best, lft->glnstx(l, h, x));
        }
        return best;
    }
} *root;


int main(){
    int n, q;
    scanf("%d %d", &n, &q);
    bks.push_back(0);
    for(int i = 0; i < n; ++i){
        int x;
        scanf("%d", &x);
        bks.push_back(x);
    }
    root = new node(1, n);
    if(n > 200005) return 0;
    for(int i = 0; i < q; ++i){
        int l, r, w;
        scanf("%d %d %d", &l, &r, &w);
        if(root->ghs(l,r) > w){
            printf("0\n");
        }else{
            printf("1\n");
        }
    }
}

Compilation message (stderr)

sortbooks.cpp: In constructor 'node::node(int, int)':
sortbooks.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             while(lp < lft->svals.size()-1 || rp < rght->svals.size()-1){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:31:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             while(lp < lft->svals.size()-1 || rp < rght->svals.size()-1){
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
sortbooks.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |         scanf("%d %d %d", &l, &r, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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