Submission #651380

#	Time	Username	Problem	Language	Result	Execution time	Memory
651380		Astrayt	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	664 ms	63172 KiB

sortbooks

//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second

struct FenwickTree{
    int n = 1000004, val[1000005];
    void modify(int p, int x){
        for(; p; p -= p&-p) val[p] = max(x, val[p]);
    }
    int query(int p){
        int ret = 0;
        for(; p <= n; p += p&-p) ret = max(ret, val[p]);
        return ret;
    }
}BIT;

struct qry{
    int l, r, k, i;
};

void solve(){
    int n, m; cin >> n >> m;
    vector<int> w(n + 1, 0), ans(m + 1, 0);
    for(int i = 1; i <= n; ++i) cin >> w[i];
    vector<qry> Q(m + 1);
    for(int i = 1; i <= m; ++i){
        auto &[l, r, k, ind] = Q[i];
        cin >> l >> r >> k;
        ind = i;
    }
    sort(Q.begin() + 1, Q.end(), [](qry q1, qry q2){return q1.r < q2.r;});
    stack<int> stk;
    for(int i = 1, j = 1; i <= n; ++i){
        while(stk.size() && w[stk.top()] <= w[i]) stk.pop();
        if(stk.size()) BIT.modify(stk.top(), w[stk.top()] + w[i]);
        while(j <= m && Q[j].r == i){
            if(Q[j].k >= BIT.query(Q[j].l)){
                ans[Q[j].i] = 1;
            }
            j++;
        }
        stk.push(i);
    }
    for(int i = 1; i <= m; ++i) cout << ans[i] << '\n';
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

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