167362025-05-11 22:34:26szilSiklóernyőzéscpp17Time limit exceeded 0/1002.101s31540 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 200'001;
int K;

struct segtree1 {
    vector<pair<int, int>> tree;
    int n;

    segtree1() {}

    segtree1(int n) : n(n) {
        tree.resize(2*n);
    }

    void upd(int u, int k) {
        tree[u + n] = {k, u};
        u += n;
        for (u /= 2; u >= 1; u /= 2) {
            tree[u] = max(tree[2*u], tree[2*u+1]);
        }
    }

    int qry(int l, int r) {
        l += n; r += n;
        pair<int, int> res = {0, 0};
        while (l <= r) {
            if (l % 2 == 1) res = max(res, tree[l++]);
            if (r % 2 == 0) res = max(res, tree[r--]);
            l /= 2; r /= 2;
        }
        return res.second;
    }
};

struct segtree2 {
    struct node {
        int mx = 0, lazy = 0;

        void apply(int x) {
            lazy += x;
        }
    };

    vector<node> tree;
    int n;

    segtree2() {}

    segtree2(int n) : n(n) {
        tree.resize(8*n);
    }

    void pull(int v) {

        node &u = tree[v];
        node &l = tree[2*v];
        node &r = tree[2*v+1];

        u.mx = max(l.mx + l.lazy, r.mx + r.lazy) + u.lazy;
    }

    void upd_add(int v, int tl, int tr, int l, int r, int val) {
        if (l > r) return;
        if (l == tl && r == tr) {
            tree[v].apply(val);
        } else {
            int tm = (tl + tr) / 2;
            upd_add(2*v, tl, tm, l, min(r, tm), val);
            upd_add(2*v+1, tm+1, tr, max(l, tm+1), r, val);
            pull(v);
        }
    }

    int qry(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        pull(v);
        if (l == tl && r == tr) {
            return tree[v].mx;
        } else {
            int tm = (tl + tr) / 2;
            return max(qry(2*v, tl, tm, l, min(r, tm)), qry(2*v+1, tm+1, tr, max(tm+1, l), r)) + tree[v].lazy;
        }
    }
};

int a[MAXN], n, q, il[MAXN], ir[MAXN], ans[MAXN], depth[MAXN], max_depth = 0;
segtree1 st_max;
segtree2 st_depth;

void calc_depth(int l, int r, int d = 0) {
    if (l > r) return;
    int u = st_max.qry(l, r);
    depth[u] = d;
    max_depth = max(max_depth, d);
    il[u] = l;
    ir[u] = r;
    calc_depth(l, u-1, d+1);
    calc_depth(u+1, r, d+1);
}

void rem(int idx) {
    st_depth.upd_add(1, 1, n, il[idx], ir[idx], -1);
}

void add(int idx) {
    st_depth.upd_add(1, 1, n, il[idx], ir[idx], 1);
}

void solve() {
    cin >> n >> q;
    K = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    st_max = segtree1(n+1);
    st_depth = segtree2(n+1);
    for (int i = 1; i <= n; i++) st_max.upd(i, a[i]);
    calc_depth(1, n);
    bool is_subtask7 = max_depth <= 70;

    vector<array<int, 3>> qrys(q);
    auto upd = [&](auto &&self, int l, int r, bool go_right, int sgn, int u = -1) -> void {
        if (l > r) return;
        if (u == -1) u = st_max.qry(l, r);
        int nl = l, nr = r;
        if (go_right) nl = u+1;
        else nr = u-1;
        int v = st_max.qry(nl, nr);
        int outside = depth[v] - depth[u] - 1;
        st_depth.upd_add(1, 1, n, nl, nr, outside * sgn);
        self(self, nl, nr, go_right, sgn, v);
    };

    if (is_subtask7) {
        for (int i = 1; i <= n; i++) st_depth.upd_add(1, 1, n, i, i, depth[i]);
    }

    for (int i = 0; i < q; i++) {
        if (is_subtask7) {
            int l, r; cin >> l >> r;
            upd(upd, l, r, 0, -1);
            upd(upd, l, r, 1, -1);
            cout << st_depth.qry(1, 1, n, l, r)-depth[st_max.qry(l, r)] << "\n";
            upd(upd, l, r, 0, 1);
            upd(upd, l, r, 1, 1);
        } else {
            cin >> qrys[i][0] >> qrys[i][1];
            qrys[i][2] = i+1;
        }
    }
    if (is_subtask7) return;
    sort(qrys.begin(), qrys.end(), [&](auto a, auto b){
        if (a[0] / K == b[0] / K) return a[1] > b[1];
        return a[0] < b[0];
    });
    int l = 1, r = 0;
    for (auto [nl, nr, idx] : qrys) {
        while (r < nr) add(++r);
        while (l > nl) add(--l);
        while (r > nr) rem(r--);
        while (l < nl) rem(l++);
        ans[idx] = st_depth.qry(1, 1, n, l, r)-1;
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Time limit exceeded2.088s21808 KiB
subtask20/5
3Time limit exceeded2.085s31540 KiB
4Time limit exceeded2.084s22324 KiB
5Time limit exceeded2.085s23604 KiB
6Time limit exceeded2.085s31540 KiB
7Time limit exceeded2.089s28152 KiB
8Accepted277ms30004 KiB
subtask30/13
9Accepted2ms564 KiB
10Accepted3ms564 KiB
11Accepted2ms572 KiB
12Accepted2ms756 KiB
13Accepted2ms564 KiB
14Accepted2ms564 KiB
15Wrong answer3ms732 KiB
16Wrong answer3ms752 KiB
17Accepted2ms820 KiB
subtask40/10
18Accepted2ms564 KiB
19Accepted3ms564 KiB
20Accepted2ms572 KiB
21Accepted2ms756 KiB
22Accepted2ms564 KiB
23Accepted2ms564 KiB
24Wrong answer3ms732 KiB
25Wrong answer3ms752 KiB
26Accepted2ms820 KiB
27Accepted94ms19024 KiB
28Accepted94ms19188 KiB
29Accepted94ms18976 KiB
30Accepted90ms19208 KiB
31Accepted90ms18996 KiB
32Accepted93ms18996 KiB
33Wrong answer150ms21556 KiB
34Wrong answer148ms21500 KiB
35Wrong answer141ms19776 KiB
36Accepted129ms26676 KiB
subtask50/15
37Accepted2ms564 KiB
38Accepted3ms564 KiB
39Accepted2ms572 KiB
40Accepted2ms756 KiB
41Accepted2ms564 KiB
42Accepted2ms564 KiB
43Wrong answer3ms732 KiB
44Wrong answer3ms752 KiB
45Accepted2ms820 KiB
46Wrong answer527ms4756 KiB
47Wrong answer500ms4660 KiB
48Wrong answer395ms4660 KiB
49Wrong answer391ms4660 KiB
50Wrong answer1.779s3628 KiB
51Wrong answer1.763s3508 KiB
52Wrong answer1.703s3568 KiB
53Wrong answer1.715s3884 KiB
54Wrong answer782ms4652 KiB
55Wrong answer754ms4640 KiB
56Wrong answer722ms4660 KiB
57Wrong answer680ms4648 KiB
subtask60/10
58Time limit exceeded2.088s21796 KiB
59Time limit exceeded2.088s22056 KiB
60Time limit exceeded2.088s21812 KiB
61Time limit exceeded2.088s22068 KiB
62Time limit exceeded2.086s22000 KiB
63Time limit exceeded2.088s22064 KiB
64Wrong answer331ms25908 KiB
65Wrong answer321ms25368 KiB
66Wrong answer314ms24120 KiB
67Wrong answer256ms26480 KiB
subtask70/11
68Accepted2ms564 KiB
69Accepted3ms564 KiB
70Accepted2ms572 KiB
71Accepted2ms756 KiB
72Accepted2ms564 KiB
73Accepted2ms564 KiB
74Wrong answer3ms732 KiB
75Wrong answer3ms752 KiB
76Accepted2ms820 KiB
77Accepted94ms19024 KiB
78Accepted94ms19188 KiB
79Accepted94ms18976 KiB
80Accepted90ms19208 KiB
81Accepted90ms18996 KiB
82Accepted93ms18996 KiB
83Wrong answer150ms21556 KiB
84Wrong answer148ms21500 KiB
85Wrong answer141ms19776 KiB
86Accepted129ms26676 KiB
87Time limit exceeded2.088s21796 KiB
88Time limit exceeded2.088s22056 KiB
89Time limit exceeded2.088s21812 KiB
90Time limit exceeded2.088s22068 KiB
91Time limit exceeded2.086s22000 KiB
92Time limit exceeded2.088s22064 KiB
93Wrong answer331ms25908 KiB
94Wrong answer321ms25368 KiB
95Wrong answer314ms24120 KiB
96Wrong answer256ms26480 KiB
97Time limit exceeded2.085s21812 KiB
98Time limit exceeded2.085s21764 KiB
99Time limit exceeded2.085s21812 KiB
100Time limit exceeded2.085s21804 KiB
101Time limit exceeded2.085s21924 KiB
102Time limit exceeded2.086s21940 KiB
103Wrong answer515ms25908 KiB
104Wrong answer492ms24628 KiB
105Wrong answer481ms24116 KiB
106Wrong answer391ms28472 KiB
subtask80/21
107Accepted1ms500 KiB
108Time limit exceeded2.088s21812 KiB
109Time limit exceeded2.088s21812 KiB
110Time limit exceeded2.088s21640 KiB
111Time limit exceeded2.101s21744 KiB
112Time limit exceeded2.085s21692 KiB
113Time limit exceeded2.085s21804 KiB
114Time limit exceeded2.084s21748 KiB
115Time limit exceeded2.101s22124 KiB
116Time limit exceeded2.088s22068 KiB
117Time limit exceeded2.088s21824 KiB
118Time limit exceeded2.088s22068 KiB
119Time limit exceeded2.101s21812 KiB
120Time limit exceeded2.091s21996 KiB
121Time limit exceeded2.089s21812 KiB
122Time limit exceeded2.091s21860 KiB
subtask90/15
123Accepted1ms500 KiB
124Time limit exceeded2.088s21812 KiB
125Time limit exceeded2.085s31540 KiB
126Time limit exceeded2.084s22324 KiB
127Time limit exceeded2.085s23604 KiB
128Time limit exceeded2.085s31540 KiB
129Time limit exceeded2.089s28152 KiB
130Accepted277ms30004 KiB
131Accepted2ms564 KiB
132Accepted3ms564 KiB
133Accepted2ms572 KiB
134Accepted2ms756 KiB
135Accepted2ms564 KiB
136Accepted2ms564 KiB
137Wrong answer3ms732 KiB
138Wrong answer3ms752 KiB
139Accepted2ms820 KiB
140Accepted94ms19024 KiB
141Accepted94ms19188 KiB
142Accepted94ms18976 KiB
143Accepted90ms19208 KiB
144Accepted90ms18996 KiB
145Accepted93ms18996 KiB
146Wrong answer150ms21556 KiB
147Wrong answer148ms21500 KiB
148Wrong answer141ms19776 KiB
149Accepted129ms26676 KiB
150Wrong answer527ms4756 KiB
151Wrong answer500ms4660 KiB
152Wrong answer395ms4660 KiB
153Wrong answer391ms4660 KiB
154Wrong answer1.779s3628 KiB
155Wrong answer1.763s3508 KiB
156Wrong answer1.703s3568 KiB
157Wrong answer1.715s3884 KiB
158Wrong answer782ms4652 KiB
159Wrong answer754ms4640 KiB
160Wrong answer722ms4660 KiB
161Wrong answer680ms4648 KiB
162Time limit exceeded2.088s21796 KiB
163Time limit exceeded2.088s22056 KiB
164Time limit exceeded2.088s21812 KiB
165Time limit exceeded2.088s22068 KiB
166Time limit exceeded2.086s22000 KiB
167Time limit exceeded2.088s22064 KiB
168Wrong answer331ms25908 KiB
169Wrong answer321ms25368 KiB
170Wrong answer314ms24120 KiB
171Wrong answer256ms26480 KiB
172Time limit exceeded2.085s21812 KiB
173Time limit exceeded2.085s21764 KiB
174Time limit exceeded2.085s21812 KiB
175Time limit exceeded2.085s21804 KiB
176Time limit exceeded2.085s21924 KiB
177Time limit exceeded2.086s21940 KiB
178Wrong answer515ms25908 KiB
179Wrong answer492ms24628 KiB
180Wrong answer481ms24116 KiB
181Wrong answer391ms28472 KiB
182Time limit exceeded2.088s21812 KiB
183Time limit exceeded2.088s21640 KiB
184Time limit exceeded2.101s21744 KiB
185Time limit exceeded2.085s21692 KiB
186Time limit exceeded2.085s21804 KiB
187Time limit exceeded2.084s21748 KiB
188Time limit exceeded2.101s22124 KiB
189Time limit exceeded2.088s22068 KiB
190Time limit exceeded2.088s21824 KiB
191Time limit exceeded2.088s22068 KiB
192Time limit exceeded2.101s21812 KiB
193Time limit exceeded2.091s21996 KiB
194Time limit exceeded2.089s21812 KiB
195Time limit exceeded2.091s21860 KiB
196Time limit exceeded2.085s24460 KiB
197Time limit exceeded2.086s24700 KiB
198Time limit exceeded2.085s24312 KiB
199Time limit exceeded2.085s23204 KiB
200Time limit exceeded2.094s23092 KiB
201Time limit exceeded2.092s22976 KiB
202Time limit exceeded2.092s22512 KiB
203Time limit exceeded2.092s22520 KiB
204Time limit exceeded2.086s22324 KiB
205Time limit exceeded2.088s22172 KiB