oj.uz

답안 #579013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579013 2022-06-18T09:51:00 Z LucaIlie Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 535 ms 262144 KB 
#include <bits/stdc++.h>
 
#define MAX_N 2000000
 
using namespace std;
 
int w[MAX_N];
 
int lower( vector <int> &v, int x ) {
    int l, r, mid;
 
    l = 0;
    r = v.size();
    while ( r - l > 1 ) {
        mid = (l + r) / 2;
 
        if ( v[mid] < x )
            l = mid;
        else
            r = mid;
    }
 
    return v[l] < x ? v[l] : -x;
}
 
 
struct AINT {
    struct nod {
        int maxEffort, maxW;
        vector <int> v;
    };
 
    struct answer {
        int maxEfort, maxW;
    };
 
    nod aint[4 * MAX_N];
    answer ans;
 
    void init( int nod, int l, int r ) {
        int mid, i, j;
 
        if ( l == r ) {
            aint[nod].maxEffort = 0;
            aint[nod].maxW = w[l];
            aint[nod].v.push_back( w[l] );
            return;
        }
 
        mid = (l + r) / 2;
        init( nod * 2 + 1, l, mid );
        init( nod * 2 + 2, mid + 1, r );
 
        aint[nod].maxW = max( aint[nod * 2 + 1].maxW, aint[nod * 2 + 2].maxW );
        aint[nod].maxEffort = max( max( aint[nod * 2 + 1].maxEffort, aint[nod * 2 + 2].maxEffort ), aint[nod * 2 + 1].maxW + lower( aint[nod * 2 + 2].v, aint[nod * 2 + 1].maxW ) );
 
        i = j = 0;
        while ( i < aint[nod * 2 + 1].v.size() && j < aint[nod * 2 + 2].v.size() ) {
            if ( aint[nod * 2 + 1].v[i] < aint[nod * 2 + 2].v[j] ) {
                aint[nod].v.push_back( aint[nod * 2 + 1].v[i] );
                i++;
            } else {
                aint[nod].v.push_back( aint[nod * 2 + 2].v[j] );
                j++;
            }
        }
        while ( i < aint[nod * 2 + 1].v.size() ) {
            aint[nod].v.push_back( aint[nod * 2 + 1].v[i] );
            i++;
        }
        while ( j < aint[nod * 2 + 2].v.size() ) {
            aint[nod].v.push_back( aint[nod * 2 + 2].v[j] );
            j++;
        }
    }
 
    void query( int nod, int l, int r, int lq, int rq ) {
        int mid;
 
        if ( nod == 0 )
            ans = { 0, 0 };
 
        if ( l > rq || r < lq )
            return;
 
        if ( lq <= l && r <= rq ) {
            ans.maxEfort = max( max( ans.maxEfort, aint[nod].maxEffort ), ans.maxW + lower( aint[nod].v, ans.maxW ) );
            ans.maxW = max( ans.maxW, aint[nod].maxW );
            return;
        }
 
        mid = (l + r) / 2;
        query( nod * 2 + 1, l, mid, lq, rq );
        query( nod * 2 + 2, mid + 1, r, lq, rq );
    }
};
 
AINT shelf;
 
int main() {
    int n, m, l, r, k, i;
 
    cin >> n >> m;
    for ( i = 0; i < n; i++ )
        cin >> w[i];
 
    shelf.init( 0, 0, n - 1 );
 
    for ( i = 0; i < m; i++ ) {
        cin >> l >> r >> k;
 
        shelf.query( 0, 0, n - 1, l - 1, r - 1 );
 
        if ( shelf.ans.maxEfort > k )
            cout << "0\n";
        else
            cout << "1\n";
    }
 
    return 0;
}

Compilation message

sortbooks.cpp: In member function 'void AINT::init(int, int, int)':
sortbooks.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         while ( i < aint[nod * 2 + 1].v.size() && j < aint[nod * 2 + 2].v.size() ) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:58:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         while ( i < aint[nod * 2 + 1].v.size() && j < aint[nod * 2 + 2].v.size() ) {
      |                                                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         while ( i < aint[nod * 2 + 1].v.size() ) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while ( j < aint[nod * 2 + 2].v.size() ) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 250732 KB Output is correct
2 Correct 132 ms 250804 KB Output is correct
3 Correct 121 ms 250796 KB Output is correct
4 Correct 127 ms 250700 KB Output is correct
5 Correct 131 ms 250708 KB Output is correct
6 Correct 127 ms 250804 KB Output is correct
7 Correct 115 ms 250824 KB Output is correct
8 Correct 130 ms 250756 KB Output is correct
9 Correct 112 ms 250708 KB Output is correct
10 Correct 121 ms 250772 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 250732 KB Output is correct
2 Correct 132 ms 250804 KB Output is correct
3 Correct 121 ms 250796 KB Output is correct
4 Correct 127 ms 250700 KB Output is correct
5 Correct 131 ms 250708 KB Output is correct
6 Correct 127 ms 250804 KB Output is correct
7 Correct 115 ms 250824 KB Output is correct
8 Correct 130 ms 250756 KB Output is correct
9 Correct 112 ms 250708 KB Output is correct
10 Correct 121 ms 250772 KB Output is correct
11 Correct 139 ms 250952 KB Output is correct
12 Correct 122 ms 251340 KB Output is correct
13 Correct 125 ms 251384 KB Output is correct
14 Correct 150 ms 251380 KB Output is correct
15 Correct 150 ms 251372 KB Output is correct
16 Correct 140 ms 251408 KB Output is correct
17 Correct 131 ms 251176 KB Output is correct
18 Correct 145 ms 251452 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 535 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 165 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 250732 KB Output is correct
2 Correct 132 ms 250804 KB Output is correct
3 Correct 121 ms 250796 KB Output is correct
4 Correct 127 ms 250700 KB Output is correct
5 Correct 131 ms 250708 KB Output is correct
6 Correct 127 ms 250804 KB Output is correct
7 Correct 115 ms 250824 KB Output is correct
8 Correct 130 ms 250756 KB Output is correct
9 Correct 112 ms 250708 KB Output is correct
10 Correct 121 ms 250772 KB Output is correct
11 Correct 139 ms 250952 KB Output is correct
12 Correct 122 ms 251340 KB Output is correct
13 Correct 125 ms 251384 KB Output is correct
14 Correct 150 ms 251380 KB Output is correct
15 Correct 150 ms 251372 KB Output is correct
16 Correct 140 ms 251408 KB Output is correct
17 Correct 131 ms 251176 KB Output is correct
18 Correct 145 ms 251452 KB Output is correct
19 Runtime error 221 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 250732 KB Output is correct
2 Correct 132 ms 250804 KB Output is correct
3 Correct 121 ms 250796 KB Output is correct
4 Correct 127 ms 250700 KB Output is correct
5 Correct 131 ms 250708 KB Output is correct
6 Correct 127 ms 250804 KB Output is correct
7 Correct 115 ms 250824 KB Output is correct
8 Correct 130 ms 250756 KB Output is correct
9 Correct 112 ms 250708 KB Output is correct
10 Correct 121 ms 250772 KB Output is correct
11 Correct 139 ms 250952 KB Output is correct
12 Correct 122 ms 251340 KB Output is correct
13 Correct 125 ms 251384 KB Output is correct
14 Correct 150 ms 251380 KB Output is correct
15 Correct 150 ms 251372 KB Output is correct
16 Correct 140 ms 251408 KB Output is correct
17 Correct 131 ms 251176 KB Output is correct
18 Correct 145 ms 251452 KB Output is correct
19 Runtime error 535 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -