Submission #1316566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316566		nekolie	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1559 ms	103260 KiB

sortbooks

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

const int M = 1000007, baza = (1<<20);
const long long inf = (1ll<<61);
int n,m, a[M], odp[M]; vector<tuple<int,long long,int>> query[M];
long long d[2*baza][2]; vector<int> ind;
void push(int v) {
    d[2*v][0] += d[v][1], d[2*v+1][0] += d[v][1];
    d[2*v][1] += d[v][1], d[2*v+1][1] += d[v][1];
    d[v][1] = 0;
}
void ustaw(int i, long long x) {
    int v = 1;
    for (int j = 19; j >= 0; j--)
        push(v), v = ((i&(1<<j)) ? 2*v+1 : 2*v);
    d[v][0] = x, v >>= 1;
    while (v > 0)
        d[v][0] = max(d[2*v][0],d[2*v+1][0]), v >>= 1;
}
void akt(int a, int b, int x, int v, int l, int r) {
    if (r < a || l > b)
        return;
    if (a <= l && r <= b)
        d[v][0] += x, d[v][1] += x;
    else
        push(v), akt(a,b,x,2*v,l,(l+r)/2), akt(a,b,x,2*v+1,(l+r)/2+1,r), d[v][0] = max(d[2*v][0],d[2*v+1][0]);
}
long long maks(int a, int b, int v, int l, int r) {
    if (r < a || l > b)
        return -inf;
    if (a <= l && r <= b)
        return d[v][0];
    else {
        push(v);
        return max(maks(a,b,2*v,l,(l+r)/2), maks(a,b,2*v+1,(l+r)/2+1,r));
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for (int i = 0; i < 2*baza; i++)
        d[i][0] = -inf;
    cin >> n >> m; int l,r,k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> l >> r >> k, query[l].push_back({r,1ll*k,i});
    a[n+1] = INT_MAX, ind.push_back(n+1);
    for (int i = n; i > 0; i--) {
        while (a[i] > a[ind.back()])
            ustaw(ind.back(),2*a[ind.back()]), akt(ind.back(),ind[ind.size()-2]-1,a[i]-a[ind.back()],1,0,baza-1), ind.pop_back();
        ind.push_back(i);
        for (auto [x,lim,j] : query[i])
            odp[j] = ((maks(i,x,1,0,baza-1) <= lim) ? 1 : 0);
    }
    for (int i = 0; i < m; i++)
        cout << odp[i] << "\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