Submission #391508

#	Time	Username	Problem	Language	Result	Execution time	Memory
391508		_eve	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	737 ms	134196 KiB

sortbooks

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)1e6 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e17 + 10;

int n, q, a[N], ans[N];
struct Q{
    int l,k,id;
    Q() {};
    Q(int _l,int _k,int _id) : l(_l), k(_k), id(_id) {};
};
vector<Q> query[N];
ll t[N];
void upd(int p,ll x,int u,int l,int r) {
    if(l == r) {
        t[u] = x;
        return;
    }
    int m = l + r >> 1;
    if(p <= m) upd(p,x,u << 1,l,m);
    else upd(p,x,u << 1 | 1,m + 1,r);
    t[u] = max(t[u << 1],t[u << 1 | 1]);
}
int get(int ql,int qr,int u,int l,int r) {
    if(ql > r || l > qr) return -1;
    if(ql <= l && r <= qr) return t[u];
    int m = l + r >> 1;
    return max(get(ql,qr,u<<1,l,m),get(ql,qr,u<<1|1,m+1,r));
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= q; i++) {
        int l,r,k; 
        cin >> l >> r >> k;
        Q x = Q(l,k,i);
        query[r].push_back(x);
    }
    stack<int> s;
    for(int i = 1; i <= n; i++) {
        while(!s.empty() && a[s.top()] <= a[i]) s.pop();
        if(!s.empty()) {
            upd(s.top(),a[s.top()] + a[i],1,1,n);
        }
        for(Q x : query[i]) {
            ans[x.id] = (get(x.l,i,1,1,n) <= x.k); 
        }
        s.push(i);
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

sortbooks.cpp: In function 'void upd(int, long long int, int, int, int)':
sortbooks.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |     int m = l + r >> 1;
      |             ~~^~~
sortbooks.cpp: In function 'int get(int, int, int, int, int)':
sortbooks.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int m = l + r >> 1;
      |             ~~^~~

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