Submission #1080271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080271		baluteshih	Bouquet (EGOI24_bouquet)	C++14	100 / 100	112 ms	7668 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())
#ifdef bbq
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int f = 0;
    (..., (cerr << (f++ ? ", " : "") << a));
    cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
    cerr << "\e[1;33m[" << s << "] = [";
    using namespace experimental;
    copy(L, R, make_ostream_joiner(cerr, ", "));
    cerr << "]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

const int MAXN = 200005;

int bit[MAXN], n;

void modify(int x, int v) {
    for (++x; x <= n; x += x & -x)
        bit[x] = max(bit[x], v);
}

int query(int x) {
    int res = 0;
    for (++x; x; x -= x & -x)
        res = max(res, bit[x]);
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    vector<pii> arr(n);
    for (auto &[l, r] : arr)
        cin >> l >> r;
    vector<int> idx(n + n);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int a, int b) {
        int vala = a < n ? a : a - n - arr[a - n].X;
        int valb = b < n ? b : b - n - arr[b - n].X;
        if (vala == valb) return a > b;
        return vala < valb;
    });
    vector<int> dp(n);
    orange(ALL(idx));
    for (int i : idx) {
        if (i < n) {
            modify(i + arr[i].Y, dp[i]);
        }
        else {
            dp[i - n] = query(i - n - 1) + 1;
        }
    }
    cout << *max_element(ALL(dp)) << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:54:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for (auto &[l, r] : arr)
      |                ^

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