Submission #1087354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087354		SulA	Bouquet (EGOI24_bouquet)	C++17	100 / 100	64 ms	17496 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;

struct segtree {
    vector<int> tree;
    int offset = 1;

    segtree(int n) {
        while (offset < n) offset <<= 1;
        tree.resize(offset << 1);
    }

    void update(int i, int x) {
        tree[i += offset] = x;
        while (i >>= 1) tree[i] = max(tree[2*i], tree[2*i + 1]);
    }

    int _query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        if (qr < l || r < ql) return 0;
        int mid = (l+r) >> 1;
        return max({
            _query(2*v, l, mid, ql, qr),
            _query(2*v + 1, mid + 1, r, ql, qr)
        });
    }

    int query(int l, int r) {
        if (r < l) return 0;
        return _query(1, 0, offset - 1, l, r);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n; cin >> n;
    int l[n], r[n];
    for (int i = 0; i < n; cin >> l[i] >> r[i++]);
    int dp[n];
    vector<int> upd[n];
    segtree s(n);
    for (int i = 0; i < n; i++) {
        dp[i] = s.query(0, i - l[i] - 1) + 1;
        if (i + r[i] < n) upd[i + r[i]].push_back(i);
        for (int ind : upd[i]) {
            s.update(ind, dp[ind]);
        }
    }
    cout << *max_element(dp, dp + n);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:45:46: warning: operation on 'i' may be undefined [-Wsequence-point]
   45 |     for (int i = 0; i < n; cin >> l[i] >> r[i++]);
      |                                             ~^~

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30