Submission #47601

#	Time	Username	Problem	Language	Result	Execution time	Memory
47601		qoo2p5	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	0 / 100	490 ms	48656 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = (int) 5e5 + 123;
const int L = 20;

struct Q {
    int t, l, r;
    
    bool operator<(const Q &b) const {
        return t < b.t;
    }
};

int n, q;
int d[N];
int sp[L][N];
int log2z[N];
Q qu[N];

int get(int l, int r) {
    int j = log2z[r - l + 1];
    return max(sp[j][l], sp[j][r - (1 << j) + 1]);
}

struct Seg {
    int x, l, r;
};

void run() {
    rep(i, 2, N) {
        log2z[i] = log2z[i / 2] + 1;
    }
    
    cin >> n >> q;
    rep(i, 1, n + 1) {
        cin >> d[i];
        sp[0][i] = d[i];
    }
    rep(j, 1, L) {
        for (int i = 0; i + (1 << j) - 1 < N; i++) {
            sp[j][i] = max(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))]);
        }
    }
    rep(i, 0, q) {
        cin >> qu[i].t >> qu[i].l >> qu[i].r;
    }
    sort(qu, qu + q);
    vector<Seg> st = {{-1, 1, n}};
    rep(i, 0, q) {
        int t = qu[i].t;
        int cnt = 0;
        while (sz(st)) {
            int left = st.back().l - 1;
            int right = st.back().r + 1;
            int p = t - cnt;
            while (right - left > 1) {
                int mid = (left + right) / 2;
                if (get(st.back().l, mid) <= p - 1 - st.back().x) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            
            if (left == st.back().l - 1) {
                break;
            }
            if (left == st.back().r) {
                cnt += st.back().r - st.back().l + 1;
                st.pop_back();
                continue;
            }
            cnt += left - st.back().l + 1;
            st.back().l += (left - st.back().l + 1);
            assert(st.back().l <= st.back().r);
            break;
        }
        
        if (cnt > 0) {
            st.pb({t - 1, 1, cnt});
        }
        
        int left = (int) (lower_bound(all(st), Seg{qu[i].l, -1, -1}, [] (auto &u, auto &v) {
            return u.x < v.x;
        }) - st.begin());
        int right = (int) (upper_bound(all(st), Seg{qu[i].r, -1, -1}, [] (auto &u, auto &v) {
            int cu = u.r - u.l;
            int cv = v.r - v.l;
            return u.x - cu < u.x - cv;
        }) - st.begin()) - 1;
        
        int res = 0;
        if (left <= right) {
            int L = min(st[left].r, st[left].l + st[left].x - qu[i].l);
            int R = max(st[right].l, st[right].l + st[left].x - qu[i].r);
            res = L - R + 1;
        }
        res += (qu[i].l <= t && t <= qu[i].r);
        cout << res << "\n";
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 81