Submission #344080

#	Time	Username	Problem	Language	Result	Execution time	Memory
344080		koketsu	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	8 / 100	3084 ms	7276 KiB

sortbooks

#include <bits/stdc++.h>
#define pb push_back
#define LL long long
#define Kultivator ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const LL Mxn = 1e6 + 7;
const LL Mod = 1e9 + 7;
const LL Inf = 1e14 + 7;

map <int, int> t;

int N, M, T[Mxn];

void upd(int v, int tl, int tr, int pos, int x){
	if (tl == tr){
		t[v] = x;
        return;
	}
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        upd(v * 2, tl, tm, pos, x);
    else
        upd(v * 2+1, tm+1, tr, pos, x);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}

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

signed main() {
    Kultivator;
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        cin >> T[i];
    }
    while(M--){
        int L, R, K;
        bool Ok = false;
        cin >> L >> R >> K;
        t.clear();
        for(int i = R; i >= L; i--){
            int Num = Max(1, 0, Mod, 0, T[i] - 1);
            if(T[i] + Num > K && Num > 0){
                Ok = true;
                break;
            }
            upd(1, 0, Mod, T[i], T[i]);
        }
        if(Ok) cout << 0 << '\n';
        else cout << 1 << '\n';
    }
}

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