oj.uz

Submission #878916

# Submission time Handle Problem Language Result Execution time Memory
878916 2023-11-25T13:37:43 Z Mr_Husanboy Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 935 ms 95884 KB 
#include <bits/stdc++.h>
using namespace std;



#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif
template<class T>
int len(T &a){
    return a.size();
}

using ll = long long;
using pii = pair<int,int>;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
string fileio = "";


mt19937 mt(time(nullptr));
const int mod = 1e9 + 7;
const int inf = 1e9;
const ll infl = 1e18;
const int maxn = 1e5 + 1;


struct SegTree{
    vector<int> tr;
    int n;

    int join(int a, int b){
        return max(a,b);
    }

    int neutral(){
        return 0;
    }

    SegTree (int _n){
        n = _n;
        tr.assign(4*n, neutral());
    }

    SegTree() {}

    void init(int _n){
        n = _n;
        tr.assign(4 * n, neutral());
    }

    void init(vector<int> &a){
        build(a);
    }

    void build(vector<int> &a, int x, int l, int r){
        if(l == r){
            tr[x] = a[l]; return;
        }
        int m = (l + r) >> 1;
        build(a, x * 2, l, m); build(a, x * 2 + 1, m + 1, r);
        tr[x] = join(tr[x*2], tr[x*2 + 1]);
    }

    void upd(int x, int l, int r, int &ind, int &val){
        if(l == r){
            tr[x] = val; return;
        }
        int m = (l+r) >> 1;
        if(ind <= m) upd(x * 2, l, m, ind, val);
        else upd(x * 2 + 1, m + 1, r, ind, val);

        tr[x] = join(tr[x*2], tr[x*2 + 1]);
    }

    int get(int x, int l, int r, int &kl, int &kr){
        if(l > kr || r < kl) return neutral();
        if(kl <= l && r <= kr) return tr[x];
        int m = (l + r) >> 1;
        return join(get(x * 2, l, m, kl, kr), get(x * 2 + 1, m + 1, r, kl, kr));
    }

    int findkth(int x, int l, int r, int k){
        if(k > tr[x]){
            return -1;
        }
        if(l == r){
            return l;
        }
        int tm = (l + r) >> 1;

        if(tr[x << 1] >= k){
            return findkth(x << 1, l, tm, k);
        }else{
            return findkth((x << 1) + 1, tm + 1, r, k - tr[x << 1]);
        }
    }

    // lessen

    void build(vector<int> a){
        n = a.size();
        tr.resize(4 * n);
        build(a, 1, 0, n - 1);
    }

    void upd(int ind, int val){
        upd(1, 0, n - 1, ind, val);
    }

    int get(int l, int r){
        return get(1, 0, n - 1, l, r);
    }

    int findkth(int k){
        return findkth(1, 0, n - 1, k);
    }

};


void solve(){
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for(auto &u : a){
        cin >> u;
    }

    SegTree t(n);

    vector<vector<tuple<int,int,int>>> qu(n);
    for(int i = 0; i < q; i ++){
        int l, r, k; cin >> l >> r >> k;
        l --; r --;
        qu[r].emplace_back(l, i, k);
    }

    stack<int> st;
    vector<int> ans(q);

    for(int i = 0; i < n; i ++){
        while(!st.empty() && a[st.top()] > a[i]){
            t.upd(i, a[st.top()] + a[i]);
            st.pop();
        }
        st.push(i);
        for(auto [l, id, k] : qu[i]){
            ans[id] = t.get(l, i) <= k;
        }
    }
    for(auto u : ans) cout << u << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    auto start = chrono::high_resolution_clock::now();
    #ifndef LOCAL
    if(fileio.size()){
        freopen((fileio + ".in").c_str(), "r", stdin);
        freopen((fileio + ".out").c_str(), "w", stdout);
    }
    #endif
    int testcases = 1;
    #ifdef Tests
    cin >> testcases;
    #endif
    while(testcases --){
        solve();
        cout << '\n';
        #ifdef LOCAL
        cout << "_________________________" << endl;
        #endif
    }
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    
    cout << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:159:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  159 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
sortbooks.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen((fileio + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         freopen((fileio + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -