Submission #424036

#	Time	Username	Problem	Language	Result	Execution time	Memory
424036		doowey	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	3070 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 10;

vector<int> E[N * 4 + 512];
int X[N];

struct Node{
    int mx;
    int res;
};

Node T[N * 4 + 512];

int F(int lim, int id){
    int iq = lower_bound(E[id].begin(), E[id].end(), lim) - E[id].begin();
    if(iq == 0) return 0;
    iq -- ;
    return lim + E[id][iq];
}

void build(int node, int cl, int cr){
    if(cl == cr){
        T[node].mx = X[cl];
        E[node].push_back(X[cl]);
        return ;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);

    int pa = 0;
    int pb = 0;
    while(pa < E[node * 2].size() || pb < E[node * 2 + 1].size()){
        if(pa < E[node * 2].size() && (pb == E[node * 2 + 1].size() || E[node * 2][pa] < E[node * 2 + 1][pb])){
            E[node].push_back(E[node * 2][pa]);
            pa ++ ;
        }
        else{
            E[node].push_back(E[node * 2 + 1][pb]);
            pb ++ ;
        }
    }

    T[node].res = max(T[node * 2].res, T[node * 2 + 1].res);
    T[node].res = max(T[node].res, F(T[node * 2].mx, node * 2 + 1));
    T[node].mx = max(T[node * 2].mx, T[node * 2 + 1].mx);
}


Node ff;

void solve(int node, int cl, int cr, int tl, int tr){
    if(node == 1){
        ff.mx = -1;
        ff.res = 0;
        //return;
    }
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        if(ff.mx == -1){
            ff = T[node];
        }
        else{
            ff.res = max(ff.res, T[node].res);
            ff.res = max(ff.res, F(ff.mx, node));
            ff.mx = max(ff.mx, T[node].mx);
        }
        return;
    }
    int mid = (cl + cr) / 2;
    solve(node * 2, cl, mid, tl, tr);
    solve(node * 2 + 1, mid + 1, cr, tl, tr);
}

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++ ){
        cin >> X[i];
    }
    build(1, 1, n);
    int li, ri;
    int lq;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> li >> ri >> lq;
        solve(1, 1, n, li, ri);
        if(ff.res > lq){
            cout << "0\n";
        }
        else{
            cout << "1\n";
        }
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:44:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     while(pa < E[node * 2].size() || pb < E[node * 2 + 1].size()){
      |           ~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:44:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     while(pa < E[node * 2].size() || pb < E[node * 2 + 1].size()){
      |                                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if(pa < E[node * 2].size() && (pb == E[node * 2 + 1].size() || E[node * 2][pa] < E[node * 2 + 1][pb])){
      |            ~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:45:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if(pa < E[node * 2].size() && (pb == E[node * 2 + 1].size() || E[node * 2][pa] < E[node * 2 + 1][pb])){
      |                                        ~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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