Submission #935460

#	Time	Username	Problem	Language	Result	Execution time	Memory
935460		qwe1rt1yuiop1	Advertisement 2 (JOI23_ho_t2)	C++14	10 / 100	406 ms	25972 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];
    for (auto [e, x] : v)
    {
        int id = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
        vec[0][id] = min(vec[0][id], e + x);
        vec[1][id] = min(vec[1][id], e - x);
    }
    seg[0].assign(c * 4 + 10, 0), seg[1] = seg[0];
    for (int i : {0, 1})
        build(i, 1, 0, c);

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

    // cerr << "ok1\n";

    for (auto [e, x] : v)
    {
        int xx = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
        if (flag[xx])
            continue;
        // cerr << "ok2\n";
        ++ans;
        flag[xx] = 1;
        // cerr << xx << "...\n";
        for (int i : {0, 1})
            vec[i][xx] = INT_MAX, upd(i, 1, 0, c, xx);
        // cerr << "ok3\n";
        while (1)
        {
            int id = qry(0, 1, 0, c, xx, c);
            if (vec[0][id] > e + x)
                break;
            // cerr << id << "...\n";
            flag[id] = 1;
            for (int i : {0, 1})
                vec[i][id] = INT_MAX, upd(i, 1, 0, c, id);
        }
        // cerr << "ok4\n";
        while (1)
        {
            int id = qry(1, 1, 0, c, 0, xx);
            if (vec[1][id] > e - x)
                break;
            // cerr << id << ' ' << vec[1][id] << "...\n";
            // cerr << e - x << '\n';
            flag[id] = 1;
            for (int i : {0, 1})
                vec[i][id] = INT_MAX, 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:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for (auto [e, x] : v)
      |               ^
Main.cpp:89:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     for (auto [e, x] : v)
      |               ^

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