Submission #1305275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305275		michael12	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	64 / 100	1283 ms	53444 KiB

sortbooks

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 2e5 + 10;
int tree[4 * maxn];
int a[maxn];
void update(int node, int start, int end, int id, int val){
    if(start == end){
        tree[node] = val;
    }
    else{
        int mid = (start + end) / 2;
        if(mid >= id){
            update(2 * node, start, mid, id, val);
        }
        else{
            update(2 * node + 1, mid + 1, end, id, val);
        }
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }
}
int query(int node, int start, int end, int l, int r){
    if(start > r || end < l) return INT_MIN;
    if(start >= l && end <= r) return tree[node];
    int mid = (start + end) / 2;
    int l1 = query(2 * node, start, mid, l, r);
    int r1 = query(2 * node + 1, mid + 1, end, l, r);
    return max(l1, r1);
}
signed main(){
     int n,m;
     cin >> n >> m;
     int w[n + 1];
     for(int i = 1; i <= n; i++){
        cin >> w[i];
     }
     vector<vector<pair<int, pair<int, int>>>> pr(n + 1);
     for(int i = 0; i < m; i++){
         int l, r, k;
         cin >> l >> r >> k;
         pr[l].push_back({r, {k, i}});
     }
     vector<int> stk;
     vector<int> ans(m);
     for(int i = n; i >= 1; i--){
        while(!stk.empty() && w[stk.back()] < w[i]){
            int u = stk.back();
            stk.pop_back();
            update(1, 0, n - 1, u, w[u] + w[i]);
        }
        stk.push_back(i);
        for(auto tt : pr[i]){
            int r1 = tt.ff;
            int k1 = tt.ss.ff;
            int ind = tt.ss.ss;
            int cst = query(1, 0, n - 1, i, r1);
            if(cst > k1){
                ans[ind] = 0;
            } 
            else{
                ans[ind] = 1;
            }
        }
     }
     for(int i = 0; i < m; i++){
        cout << ans[i] << endl;
     }
}

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