Submission #935475

#	Time	Username	Problem	Language	Result	Execution time	Memory
935475		qwe1rt1yuiop1	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	980 ms	131572 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

vector<int> seg[2], vec[2];

void build(int id, int x, int l, int r)
{
    if (l + 1 == r)
    {
        seg[id][x] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(id, x << 1, l, mid), build(id, x << 1 | 1, mid, r);
    if (vec[id][seg[id][x << 1]] <= vec[id][seg[id][x << 1 | 1]])
        seg[id][x] = seg[id][x << 1];
    else
        seg[id][x] = seg[id][x << 1 | 1];
}
int qry(int id, int x, int l, int r, int ql, int qr)
{
    // cerr << "ok6\n";
    // cerr << id << ' ' << x << ' ' <<  l << ' ' << ql << ' ' << qr << '\n';
    if (ql <= l && r <= qr)
        return seg[id][x];
    int mid = (l + r) >> 1;
    if (qr <= mid)
        return qry(id, x << 1, l, mid, ql, qr);
    if (ql >= mid)
        return qry(id, x << 1 | 1, mid, r, ql, qr);
    int retl = qry(id, x << 1, l, mid, ql, qr), retr = qry(id, x << 1 | 1, mid, r, ql, qr);
    if (vec[id][retl] <= vec[id][retr])
        return retl;
    return retr;
}
void upd(int id, int x, int l, int r, int idx)
{
    if (l + 1 == r)
    {
        seg[id][x] = l;
        return;
    }
    int mid = (l + r) >> 1;
    if (idx < mid)
        upd(id, x << 1, l, mid, idx);
    else
        upd(id, x << 1 | 1, mid, r, idx);
    if (vec[id][seg[id][x << 1]] <= vec[id][seg[id][x << 1 | 1]])
        seg[id][x] = seg[id][x << 1];
    else
        seg[id][x] = seg[id][x << 1 | 1];
}

void solve()
{
    int n;
    cin >> n;
    vector<pii> v(n);
    for (auto &[e, x] : v)
        cin >> x >> e;
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    vector<int> tmp;
    for (auto [e, x] : v)
        tmp.emplace_back(x);
    sort(tmp.begin(), tmp.end());
    tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());

    int c = tmp.size();

    vec[0].assign(c, INT_MAX), vec[1] = vec[0];
    vector<set<pii>> st[2];
    st[0].resize(n);
    for (int i = 0; i < n; ++i)
        st[0][i].clear();
    st[1] = st[0];
    for (int i = 0; i < n; ++i)
    {
        auto [e, x] = v[i];
        int id = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
        vec[0][id] = min(vec[0][id], e + x);
        st[0][id].emplace(e + x, i);
        vec[1][id] = min(vec[1][id], e - x);
        st[1][id].emplace(e - x, i);
    }
    seg[0].assign(c * 4 + 10, 0), seg[1] = seg[0];
    for (int i : {0, 1})
        build(i, 1, 0, c);

    vector<int> flag(n, 0);
    int ans = 0;

    for (int iii = 0; iii < n; ++iii)
    {
        if (flag[iii])
            continue;
        flag[iii] = 1;
        ++ans;
        auto [e, x] = v[iii];

        // for (int j = iii + 1; j < n; ++j)
        // {
        //     auto [ej, xj] = v[j];
        //     if (e + x >= ej + xj && xj >= x || e - x >= ej - xj && xj <= x)
        //         flag[j] = 1;
        // }
        // continue;
                

        int xx = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
        // st[0][xx].erase({e + x, iii});
        // st[1][xx].erase({e - x, iii});
        for (int i : {0, 1})
        {
            for (auto [vall, ii] : st[i][xx])
                flag[ii] = 1;
            st[i][xx].clear();
            int val = INT_MAX;
            if (!st[i][xx].empty())
                val = st[i][xx].begin()->first;
            vec[i][xx] = val, upd(i, 1, 0, c, xx);
        }
        // cerr << "ok1 " << iii << '\n';
        while (1)
        {
            int id = qry(0, 1, 0, c, xx, c);
            if (vec[0][id] > e + x)
                break;
            auto [val, iiii] = *st[0][id].begin();
            // cerr << "ok3 " << iiii << '\n';
            flag[iiii] = 1;
            auto [eeee, xxxx] = v[iiii];
            st[0][id].erase({eeee + xxxx, iiii});
            st[1][id].erase({eeee - xxxx, iiii});
            for (int i : {0, 1})
            {
                int val = INT_MAX;
                if (!st[i][id].empty())
                    val = st[i][id].begin()->first;
                vec[i][id] = val, upd(i, 1, 0, c, id);
            }
        }
        // cerr << "ok2 " << iii << '\n';
        if (xx > 0)
        {
            while (1)
            {
                int id = qry(1, 1, 0, c, 0, xx);
                if (vec[1][id] > e - x)
                    break;
                auto [val, iiii] = *st[1][id].begin();
                // cerr << "ok4 " << iiii << '\n';
                flag[iiii] = 1;
                auto [eeee, xxxx] = v[iiii];
                st[0][id].erase({eeee + xxxx, iiii});
                st[1][id].erase({eeee - xxxx, iiii});
                for (int i : {0, 1})
                {
                    int val = INT_MAX;
                    if (!st[i][id].empty())
                        val = st[i][id].begin()->first;
                    vec[i][id] = val, upd(i, 1, 0, c, id);
                }
            }
        }
    }
    cout << ans << '\n';
}

/*
4
4 2
2 3
3 4
6 5

3
7 10
10 10
7 10

 */

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:60:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for (auto &[e, x] : v)
      |                ^
Main.cpp:66:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for (auto [e, x] : v)
      |               ^
Main.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |         auto [e, x] = v[i];
      |              ^
Main.cpp:101:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |         auto [e, x] = v[iii];
      |              ^
Main.cpp:117:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |             for (auto [vall, ii] : st[i][xx])
      |                       ^
Main.cpp:131:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |             auto [val, iiii] = *st[0][id].begin();
      |                  ^
Main.cpp:134:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |             auto [eeee, xxxx] = v[iiii];
      |                  ^
Main.cpp:153:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |                 auto [val, iiii] = *st[1][id].begin();
      |                      ^
Main.cpp:156:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |                 auto [eeee, xxxx] = v[iiii];
      |                      ^

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31