제출 #697469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697469		hyakup	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3080 ms	222744 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, maxi = -inf; 
    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;
    
    // cout << " ---------- " << ini << " " << fim << " " << mid << endl;
    int pl = 0, pr = 0;
    int maxi = -inf, maxi2 = -inf, maxsum = -inf;
    
    // cout << "l: ";
    
    // for( query cur : left ) cout << cur.l << " ";
    // cout << endl;
    // cout << "r: ";
    // for( query cur : right ) cout << cur.r << " ";
    // cout << endl;
    
    while( pl < left.size() && left[pl].l > mid ) pl++;
    while( pr < right.size() && right[pr].r <= mid ) pr++;
    
    // cout << pl << " " << pr << "----" << endl;
    
    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;
            
            queries[ left[pl].id ].maxi = maxi;
            
            // cout << "-> " << left[pl].id << " " << resp[ left[pl].id ] << endl;
            pl++;
        }
    }
    // cout << "---" << endl;
    
    set<int> s;
    maxi = -inf, maxi2 = -inf, maxsum = -inf;
    
    for( int i = mid + 1; i <= fim; i++ ){
        
        s.insert(v[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;
            
            auto it = s.lower_bound( queries[ right[pr].id ].maxi );
            if( it != s.begin() ){
                it--;
                if( right[pr].k < queries[ right[pr].id ].maxi + *it ) resp[ right[pr].id ] = false;
            }
            
            queries[ right[pr].id ].maxi = -inf;
            
            // cout << "-> " << right[pr].id << " " << resp[ right[pr].id ] << endl;
            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(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    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;
        
        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] << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

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