Submission #154497

#	Time	Username	Problem	Language	Result	Execution time	Memory
154497		Pankin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1841 ms	79012 KiB

sortbooks

#include <bits/stdc++.h>

/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define con continue
#define pii pair<int, int>
#define all(x) x.begin(), x.end()

const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;

vector< pair<int, int> > dir = {
    {
        -1, 0
    },
    {
        0, 1
    },
    {
        1, 0
    },
    {
        0, -1
    }
};

bool valid(int x, int y, int n, int m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

const int N = 1000000 + 5;
int order[N], l[N], r[N], k[N], t[4 * N], a[N], ans[N], nxt[N], n, m;
stack<int> st;

inline void init() {
    for (int i = 0; i < 4 * N; i++)
        t[i] = -1;
    for (int i = 0; i < N; i++)
        nxt[i] = -1;
}

void add(int v, int tl, int tr, int pos, int val) {
    if (!(pos >= tl && pos <= tr))
        return;
    t[v] = max(t[v], val);
    if (tl == tr)
        return;
    int tm = (tl + tr) / 2;
    add(v * 2, tl, tm, pos, val);
    add(v * 2 + 1, tm + 1, tr, pos, val);
}

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

bool comp(int x, int y) {
    return r[x] < r[y];
}

signed main() {
    fast_io;

    init();

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++) {
        cin >> l[i] >> r[i] >> k[i];
        l[i]--, r[i]--;
        order[i] = i;
    }
    sort(order, order + m, comp);

    for (int i = 0; i < n; i++) {
        while(!st.empty() && a[st.top()] <= a[i])
            st.pop();
        if (!st.empty())
            nxt[i] = st.top();
        st.push(i);
    }

    int pointer = -1;

    for (int v = 0; v < m; v++) {
        int i = order[v];
        while(pointer < r[i]) {
            pointer++;
            if (nxt[pointer] != -1)
                add(1, 0, n - 1, nxt[pointer], a[nxt[pointer]] + a[pointer]);
        }
        ans[i] = (getMax(1, 0, n - 1, l[i], r[i]) <= k[i]);
    }
    for (int i = 0; i < m; i++)
        cout << ans[i] << endl;

    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