oj.uz

답안 #908672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
908672 2024-01-16T16:21:22 Z SalihSahin Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 3000 ms 262144 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
using namespace std;
 
const int mod = 1e9 + 7;
const int inf = 1e12*2;
const int N = 2e5 + 5;

struct node{
    int mx, calc;
    node(){
        mx = calc = 0;
    }
};

node merge(node a, node b, vector<int> &arr){
    node res;
    res.mx = max(a.mx, b.mx);
    res.calc = max(a.calc, b.calc);
    if(arr[0] < a.mx){
        auto x = lower_bound(arr.begin(), arr.end(), a.mx) - arr.begin();
        x--;
        res.calc = max(res.calc, arr[x] + a.mx);
    }

    return res;
}

struct SEGT{
    vector<node> tree;
    vector<vector<int> > list;
    int S;

    void init(int n){
        tree.assign(4*n, node());
        list.resize(4*n);
        S = n;
    }

    void build(int ind, int l, int r, vector<int> &a){
        if(l == r){
            list[ind].pb(a[l]);
            tree[ind].mx = a[l];
        }
        else{
            int m = (l + r)/2;

            build(ind*2, l, m, a);
            build(ind*2+1, m+1, r, a);

            int il = 0, ir = 0;
            while(il < list[ind*2].size() && ir < list[ind*2+1].size()){
                if(list[ind*2][il] <= list[ind*2+1][ir]){
                    list[ind].pb(list[ind*2][il]);
                    il++;
                }
                else{
                    list[ind].pb(list[ind*2+1][ir]);
                    ir++;
                }
            }
            while(il < list[ind*2].size()){
                list[ind].pb(list[ind*2][il]);
                il++;
            }
            while(ir < list[ind*2+1].size()){
                list[ind].pb(list[ind*2+1][ir]);
                ir++;
            }

            tree[ind] = merge(tree[ind*2], tree[ind*2+1], list[ind*2+1]);
        }
    }

    int querylist(int ind, int l, int r, int ql, int qr, int k){
        if(l > r || l > qr || r < ql) return 0;
        if(l >= ql && r <= qr){
            if(list[ind][0] >= k) return 0;

            auto x = lower_bound(list[ind].begin(), list[ind].end(), k) - list[ind].begin();
            x--;
            return list[ind][x];
        }
        else{
            int m = (l + r)/2;
            return max(querylist(ind*2, l, m, ql, qr, k), querylist(ind*2+1, m+1, r, ql, qr, k));            
        }
    }

    int query(int ind, int l, int r, int ql, int qr){
        if(l > r || l > qr || r < ql) return 0;
        if(l >= ql && r <= qr){

            int gh = querylist(1, 1, S, r, qr, tree[ind].mx);
            int val = tree[ind].calc;
            if(gh != 0 && tree[ind].mx > gh){
                val = max(val, tree[ind].mx + gh);
            }

            return val;
        }
        else{
            int m = (l + r)/2;
            return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));            
        }
    }
};
 
int32_t main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int n, q;
    cin>>n>>q;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    SEGT seg;
    seg.init(n);
    seg.build(1, 1, n, a);

    while(q--){
        int l, r, k;
        cin>>l>>r>>k;

        int val = seg.query(1, 1, n, l, r);
        if(val <= k) cout<<1<<endl;
        else cout<<0<<endl;
    }
    return 0;
}

Compilation message

sortbooks.cpp: In member function 'void SEGT::build(long long int, long long int, long long int, std::vector<long long int>&)':
sortbooks.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while(il < list[ind*2].size() && ir < list[ind*2+1].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:54:49: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while(il < list[ind*2].size() && ir < list[ind*2+1].size()){
      |                                              ~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:64:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             while(il < list[ind*2].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:68:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             while(ir < list[ind*2+1].size()){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 12 ms 860 KB Output is correct
12 Correct 16 ms 2140 KB Output is correct
13 Correct 17 ms 2140 KB Output is correct
14 Correct 32 ms 2472 KB Output is correct
15 Correct 26 ms 2392 KB Output is correct
16 Correct 17 ms 2396 KB Output is correct
17 Correct 15 ms 1628 KB Output is correct
18 Correct 17 ms 2140 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1092 ms 40152 KB Output is correct
2 Correct 1162 ms 39892 KB Output is correct
3 Correct 686 ms 39876 KB Output is correct
4 Correct 637 ms 39964 KB Output is correct
5 Correct 623 ms 40024 KB Output is correct
6 Correct 611 ms 39624 KB Output is correct
7 Correct 619 ms 39848 KB Output is correct
8 Correct 538 ms 39664 KB Output is correct
9 Correct 175 ms 2008 KB Output is correct
10 Correct 535 ms 40944 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 12 ms 860 KB Output is correct
12 Correct 16 ms 2140 KB Output is correct
13 Correct 17 ms 2140 KB Output is correct
14 Correct 32 ms 2472 KB Output is correct
15 Correct 26 ms 2392 KB Output is correct
16 Correct 17 ms 2396 KB Output is correct
17 Correct 15 ms 1628 KB Output is correct
18 Correct 17 ms 2140 KB Output is correct
19 Execution timed out 3013 ms 83776 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 12 ms 860 KB Output is correct
12 Correct 16 ms 2140 KB Output is correct
13 Correct 17 ms 2140 KB Output is correct
14 Correct 32 ms 2472 KB Output is correct
15 Correct 26 ms 2392 KB Output is correct
16 Correct 17 ms 2396 KB Output is correct
17 Correct 15 ms 1628 KB Output is correct
18 Correct 17 ms 2140 KB Output is correct
19 Runtime error 272 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -