oj.uz

Submission #707383

# Submission time Handle Problem Language Result Execution time Memory
707383 2023-03-09T00:32:04 Z hyakup Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 100488 KB 
#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(){
    
    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 );
        }
        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 20 ms 47256 KB Output is correct
2 Correct 20 ms 47188 KB Output is correct
3 Incorrect 21 ms 47248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47256 KB Output is correct
2 Correct 20 ms 47188 KB Output is correct
3 Incorrect 21 ms 47248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 100488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 335 ms 53948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47256 KB Output is correct
2 Correct 20 ms 47188 KB Output is correct
3 Incorrect 21 ms 47248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47256 KB Output is correct
2 Correct 20 ms 47188 KB Output is correct
3 Incorrect 21 ms 47248 KB Output isn't correct
4 Halted 0 ms 0 KB -