Submission #952784

#	Time	Username	Problem	Language	Result	Execution time	Memory
952784		idiotcomputer	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	100 / 100	723 ms	93140 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define f first 
#define s second

const int mxN = 1e6;

int n;
int bit[mxN+1];

void upd(int x, int v){
    while (x > 0){
      //  cout << x << '\n';
        bit[x] = max(bit[x],v);
        x -= ((~x+1) & x);
    }
}

int query(int x){
    int res = 0;
    while (x <= n){
       // cout << x << '\n';
        res = max(res,bit[x]);
        x += ((~x+1) & x);
    }
    return res;
}

struct qu {
    int l,r,k,idx;
};

int main()
{
    memset(bit,0,sizeof(bit));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int m;
    cin >> n >> m;
    
    int vals[n+1];
    vector<qu> all[n+1];
    for (int i =1; i <= n; i++) cin >> vals[i];
    vals[0] = 1e9+1;
    
    bitset<mxN> ans;
    qu temp;
    for (int i =0; i < m; i++){
        cin >> temp.l >> temp.r >> temp.k;
        temp.idx = i;
        all[temp.r].pb(temp);
    }
  //  cout << "Read\n";
    
    stack<int> curr;
    curr.push(0);
    for (int i = 1; i <= n; i++){
        while (vals[curr.top()] <= vals[i]) curr.pop();
        upd(curr.top(),vals[curr.top()]+vals[i]);
        curr.push(i);
        
        for (qu c : all[i]){
            ans[c.idx] = query(c.l) <= c.k;
        }
    }
    for (int i =0; i < m; i++) cout << ans[i] << "\n";
    
    return 0;
}

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