Submission #241559

#	Time	Username	Problem	Language	Result	Execution time	Memory
241559		valerikk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1715 ms	120664 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld; // typedef double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<ld> vd;
typedef vector<vd> vvd;
typedef complex<ld> cd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef string str;
#define int ll

template<class A, class B>
inline bool mmin(A& a, B b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

template<class A, class B>
inline bool mmax(A& a, B b) {
    if (b > a) {
        a = b;
        return 1;
    }
    return 0;
}

ld nxt_ld() {
    string s;
    cin >> s;
    return stold(s);
}

#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ef emplace_front
#define ppb pop_back
#define ppf pop_front
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const int N = 1e6 + 15, NN = 1e6 + 10;

int t[4 * N];

void upd(int v, int l, int r, int i, int x) {
    if (r - l == 1) mmax(t[v], x); else {
        int m = (l + r) / 2;
        if (i < m) upd(2 * v, l, m, i, x); else upd(2 * v + 1, m, r, i, x);
        t[v] = max(t[2 * v], t[2 * v + 1]);
    }
}

int get(int v, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) return 0;
    if (tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm, tr, l, r));
}

signed main() {
    /*freopen("cbarn.in", "r", stdin);
    freopen("cbran.out", "w", stdout);*/
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vi w(n);
    for (int i = 0; i < n; i++) cin >> w[i];
    vi go(n, -1), st;
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && w[i] > w[st.back()]) {
            go[st.back()] = i;
            st.pop_back();
        }
        st.pb(i);
    }
    vi num(n);
    for (int i = 0; i < n; i++) num[i] = go[i] == -1 ? 0 : w[i] + w[go[i]];
    vi l(m), r(m), k(m);
    vvi atr(n + 1);
    vi ans(m, 1);
    for (int i = 0; i < m; i++) {
        cin >> l[i] >> r[i] >> k[i];
        l[i]--;
        atr[r[i]].pb(i);
    }
    for (int i = 0; i <= n; i++) {
        for (auto j : atr[i]) {
            if (get(1, 0, N, l[j] + 1, N) > k[j]) ans[j] = 0;
        }
        if (i != n) upd(1, 0, N, go[i] + 1, num[i]);
    }
    for (auto x : ans) cout << x << '\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