Submission #707387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
707387	2023-03-09T00:39:41 Z	hyakup	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	2786 ms	110116 KB

sortbooks

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

const int maxn = 1e6 + 10;
const int inf = 1e9 + 10;

int v[maxn];
bool resp[maxn];

struct evento{
    
    int l, r, k, val, id, t;
    evento( int l, int r, int k, int id, int t ) : l(l), r(r), k(k), id(id), t(t) {}
    evento( int l, int val, int t ) : l(l), val(val), t(t) {}
    bool operator < ( evento e ){
        if( l == e.l ) return t < e.t;
        return l > e.l;
    }
};
vector<evento> line;
stack< pair< int, int > > s;

struct node{
    int max_val, max_inv = 0, lz = 0;
    node(){}
    
    node operator + ( node n ){
        node resp;
        
        resp.max_val = max( max_val, n.max_val );
        resp.max_inv = max( max_inv, n.max_inv );
        return resp;
    }
};

node seg[4*maxn];

void build( int pos, int ini, int fim ){
    if( ini == fim ){
        seg[pos].max_val = v[ini];
        return;
    }
    int mid = ( ini + fim )/2;
    int l = 2*pos, r = 2*pos + 1;
    
    build( l, ini, mid );
    build( r, mid + 1, fim );
    
    seg[pos] = seg[l] + seg[r];
}

void refresh( int pos, int ini, int fim ){
    if( seg[pos].lz == 0 ) return;
    int s = seg[pos].lz;
    seg[pos].lz = 0;
    seg[pos].max_inv = seg[pos].max_val + s;
    
    if( ini == fim ) return;
    int l = 2*pos, r = 2*pos + 1;
    seg[l].lz = s;
    seg[r].lz = s;
}

void update( int pos, int ini, int fim, int ki, int kf, int val ){
    refresh( pos, ini, fim );
    if( ki > fim || ini > kf ) return;
    if( ki <= ini && fim <= kf ){
        seg[pos].lz = val;
        refresh( pos, ini, fim );
        return;
    }
    int mid = ( ini + fim )/2;
    int l = 2*pos, r = 2*pos + 1;
    
    update( l, ini, mid, ki, kf, val );
    update( r, mid + 1, fim, ki, kf, val );
    
    seg[pos] = seg[l] + seg[r];
}

int query( int pos, int ini, int fim, int ki, int kf ){
    refresh( pos, ini, fim );
    if( ki > fim || ini > kf ) return -1;
    if( ki <= ini && fim <= kf ) return seg[pos].max_inv;
    int mid = ( ini + fim )/2;
    int l = 2*pos, r = 2*pos + 1;
    
    int queryL = query( l, ini, mid, ki, kf );
    int queryR = query( r, mid + 1, fim, ki, kf );
    
    return max( queryL, queryR );
} 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m; cin >> n >> m;
    for( int i = 1; i <= n; i++ ){
        cin >> v[i];
        line.push_back( evento( i, v[i], 1 ) );
    }
    for( int i = 1; i <= m; i++ ){
        int l, r, k; cin >> l >> r >> k;
        line.push_back( evento( l, r, k, i, 2 ) );
    }
    sort( line.begin(), line.end() );
    s.push({ inf, n + 1 });
    
    for( evento e : line ){
        if( e.t == 1 ){
            while( s.top().first < e.val ) s.pop();
            update( 1, 1, n, e.l + 1, s.top().second - 1, e.val );
            s.push({ e.val, e.l });
        }
        else{
            int inv = query( 1, 1, n, e.l, e.r );
            resp[ e.id ] = ( inv <= e.k );
        }
    }
    
    for( int i = 1; i <= m; i++ ) cout << resp[i] << endl;
}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	47220 KB	Output is correct
2	Correct	25 ms	47188 KB	Output is correct
3	Incorrect	26 ms	47344 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	47220 KB	Output is correct
2	Correct	25 ms	47188 KB	Output is correct
3	Incorrect	26 ms	47344 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2619 ms	101212 KB	Output is correct
2	Correct	2662 ms	101924 KB	Output is correct
3	Correct	2658 ms	102004 KB	Output is correct
4	Correct	2786 ms	101932 KB	Output is correct
5	Correct	2562 ms	110116 KB	Output is correct