Submission #1110590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110590		Zero_OP	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	1200 ms	116320 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

struct segment_tree{
    vector<int> st;
    segment_tree(int n) : st(n << 2) {}

    void build(int id, int l, int r){
        if(l == r) st[id] = 1;
        else{
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    void update(int id, int l, int r, int pos, int val){
        if(l == r) st[id] = val;
        else{
            int mid = l + r >> 1;
            if(pos <= mid) update(id << 1, l, mid, pos, val);
            else update(id << 1 | 1, mid + 1, r, pos, val);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    int walk(int id, int l, int r, int k){
        if(l == r) return l;
        int mid = l + r >> 1;
        if(st[id << 1] < k) return walk(id << 1 | 1, mid + 1, r, k - st[id << 1]);
        else return walk(id << 1, l, mid, k);
    }

    int query(int id, int l, int r, int u, int v){
        if(v < l || u > r) return 0;
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<int> a(N);
    vector<pair<int, int>> w(N);
    for(int i = 0; i < N; ++i){
        cin >> a[i];
        w[i] = {a[i], i};
    }

    vector<tuple<int, int, int, int>> queries;
    for(int i = 0; i < M; ++i){
        int l, r, k;
        cin >> l >> r >> k;
        --l, --r;
        queries.emplace_back(k, l, r, i);
    }

    //Firstly for each query , find the smallest position p that w[p] > k
    sort(queries.begin(), queries.end());
    sort(w.begin(), w.end());

    vector<bool> answer(M, false);

    segment_tree st(N);
    st.build(1, 0, N - 1);

    vector<vector<pair<int, int>>> next_phase(N);
    int j = 0;
    for(auto [k, l, r, id] : queries){
        while(j < N && w[j].first <= k){
            st.update(1, 0, N - 1, w[j++].second, -1);
        }

        int cur = (l > 0 ? st.query(1, 0, N - 1, 0, l - 1) : 0);
        int pos = st.walk(1, 0, N - 1, cur) + 1;

        if(pos > r) answer[id] = true;
        else{
            next_phase[pos].emplace_back(r, id);
        }
    }

    for(int i = N - 1, last = N - 1; i >= 0; --i){
        if(i + 1 < N && a[i] > a[i + 1]) last = i;
        for(auto [r, id] : next_phase[i]){
            if(r <= last) answer[id] = true;
        }
    }

    for(auto it : answer){
        cout << it << '\n';
    }

    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In member function 'void segment_tree::build(int, int, int)':
sortbooks.cpp:12:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |             int mid = l + r >> 1;
      |                       ~~^~~
sortbooks.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
sortbooks.cpp:22:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             int mid = l + r >> 1;
      |                       ~~^~~
sortbooks.cpp: In member function 'int segment_tree::walk(int, int, int, int)':
sortbooks.cpp:31:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         int mid = l + r >> 1;
      |                   ~~^~~
sortbooks.cpp: In member function 'int segment_tree::query(int, int, int, int, int)':
sortbooks.cpp:39:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid = l + r >> 1;
      |                   ~~^~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |     for(auto [k, l, r, id] : queries){
      |              ^
sortbooks.cpp:93:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |         for(auto [r, id] : next_phase[i]){
      |                  ^

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