제출 #349343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349343		Sara	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	2031 ms	86972 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define ll unsigned long long
#define F first
#define S second
#define pb push_back
#define lc (ind << 1)
#define rc (lc | 1)
#define md ((b + e) >> 1)
#define poo pair < int, pair <int, int> >

const ll N = 1e6 + 5;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;

string s;
int n, a[N], q, L[N], P[N];
int mx[4 * N], maxi[4 * N];
vector <int> all[N];
bool ans[N];

void add(int l, int r, int id, int b = 0, int e = n, int ind = 1){
    if (l <= b && e <= r){
        if (a[id] < mx[ind]){
            maxi[ind] = max(maxi[ind], a[id] + mx[ind]);
        }
        return;
    }
    if (l < md) add(l, r, id, b, md, lc);
    if (md < r) add(l, r, id, md, e, rc);
    maxi[ind] = max(maxi[lc], maxi[rc]); 
    return;
}

void push(int id, int b = 0, int e = n, int ind = 1){
    if (b + 1 == e){
        mx[ind] = a[b];
        return;
    }
    if (id < md) push(id, b, md, lc);
    else push(id, md, e, rc);
    mx[ind] = max(mx[lc], mx[rc]);
    return;
}

int get(int l, int r, int b = 0, int e = n, int ind = 1){
    if (l <= b && e <= r) return maxi[ind];
    int ret = 0;
    if (l < md) ret = max(ret, get(l, r, b, md, lc));
    if (md < r) ret = max(ret, get(l, r, md, e, rc));
    return ret; 
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i ++){
        cin >> a[i];
    }
    for (int i = 0; i < q; i ++){
        int R;
        cin >> L[i] >> R >> P[i]; L[i] --;
        all[R].pb(i);
    }
    push(0);
    for (int i = 1; i <= n; i ++){
        if (i != n){
            push(i);
            add(0, i, i);
        }
        for (int id : all[i]){
            ans[id] = (get(L[id], i) <= P[id]);
        }
    }
    for (int i = 0; i < q; i ++){
        cout << ans[i] << '\n';
    }
    return 0;
}         

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