Submission #697463

#	Time	Username	Problem	Language	Result	Execution time	Memory
697463		hyakup	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3079 ms	255176 KiB

sortbooks

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

const int maxn = 1e6 + 10;
const int inf = 1e9 + 10;
int v[maxn];
bool resp[maxn], active[maxn];

struct query{
    
    int l, r, k, id; 
    query( int l = 0, int r = 0, int k = 0, int id = 0) : l(l), r(r), k(k), id(id) {}
    
};

vector<query> q1, q2, queries;

bool cmp1( query a, query b ){
    
    return a.l > b.l;
}

bool cmp2( query a, query b ){
    
    return a.r < b.r;
}

void calcula( int ini, int fim, vector<query> left, vector<query> right ){
    
    if( ini > fim ) return;
    
    int mid = ( ini + fim )/2;
    int pl = 0, pr = 0;
    int maxi = -inf, maxi2 = -inf, maxsum = -inf;
    
    while( pl < left.size() && left[pl].l > mid ) pl++;
    while( pr < right.size() && right[pr].r <= mid ) pr++;
    
    for( int i = mid; i >= ini; i-- ){
        
        if( v[i] > maxi ){
            swap( maxi, maxi2 );
            maxi = v[i];
            maxsum = maxi + maxi2;
        }
        else if( v[i] > maxi2 ){
            maxi2 = v[i];
            maxsum = maxi + maxi2;
        }
        
        while( pl < left.size() && left[pl].l <= i ){
            if( queries[ left[pl].id ].r < mid ){ pl++; continue; }
            if( left[pl].k < maxsum ) resp[ left[pl].id ] = false;
            pl++;
        }
    }
    
    for( int i = mid + 1; i <= fim; i++ ){
        
        if( v[i] > maxi ){
            maxi = v[i];
            maxi2 = -inf;
        }
        else if( v[i] > maxi2 ){
            maxi2 = v[i];
            maxsum = max( maxsum, maxi + maxi2 );
        }
        
        while( pr < right.size() && right[pr].r == i ){
            if( queries[ right[pr].id ].l > mid ){ pr++; continue; }
            if( right[pr].k < maxsum ) resp[ right[pr].id ] = false;
            pr++;
        }
    }
    
    vector<query> l1, l2, r1, r2;
    
    for( query cur : left ){
        if( cur.l < mid ) l1.push_back( cur );
        else if( cur.l > mid ) l2.push_back( cur );
    }
    
    for( query cur : right ){
        if( queries[ cur.id ].l < mid ){
            
            queries[cur.id].r = min( mid - 1, queries[cur.id].r );
            cur.r = min( mid - 1, cur.r );
            r1.push_back( cur );
            
        }
        else if(  queries[ cur.id ].l > mid ) r2.push_back( cur );
    }
    
    calcula( ini, mid - 1, l1, r1 );
    calcula( mid + 1, fim, l2, r2 );
}

int main(){
    
    int n, m; cin >> n >> m;
    queries.emplace_back();
    
    for( int i = 1; i <= n; i++ ) cin >> v[i];
    for( int i = 1; i <= m; i++ ){
        int l, r, k; cin >> l >> r >> k;
        
        resp[i] = true;
        active[i] = true;
        
        q1.push_back( query( l, r, k, i ) );
        q2.push_back( query( l, r, k, i ) );
        queries.push_back( query( l, r, k, i ) );
    }
    
    sort( q1.begin(), q1.end(), cmp1 );
    sort( q2.begin(), q2.end(), cmp2 );
    
    calcula( 1, n, q1, q2 );
    
    for( int i = 1; i <= m; i++ ) cout << resp[i] << endl;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void calcula(int, int, std::vector<query>, std::vector<query>)':
sortbooks.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while( pl < left.size() && left[pl].l > mid ) pl++;
      |            ~~~^~~~~~~~~~~~~
sortbooks.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while( pr < right.size() && right[pr].r <= mid ) pr++;
      |            ~~~^~~~~~~~~~~~~~
sortbooks.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         while( pl < left.size() && left[pl].l <= i ){
      |                ~~~^~~~~~~~~~~~~
sortbooks.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         while( pr < right.size() && right[pr].r == i ){
      |                ~~~^~~~~~~~~~~~~~

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