oj.uz

Submission #935461

# Submission time Handle Problem Language Result Execution time Memory
935461 2024-02-29T07:07:12 Z qwe1rt1yuiop1 Advertisement 2 (JOI23_ho_t2) C++14
10 / 100
 379 ms 25972 KB 
#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";
        if (xx > 0)
            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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 93 ms 7124 KB Output is correct
3 Correct 90 ms 5712 KB Output is correct
4 Correct 115 ms 6252 KB Output is correct
5 Correct 58 ms 5184 KB Output is correct
6 Correct 379 ms 25972 KB Output is correct
7 Correct 262 ms 15444 KB Output is correct
8 Correct 123 ms 6548 KB Output is correct
9 Correct 88 ms 6348 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 93 ms 7124 KB Output is correct
3 Correct 90 ms 5712 KB Output is correct
4 Correct 115 ms 6252 KB Output is correct
5 Correct 58 ms 5184 KB Output is correct
6 Correct 379 ms 25972 KB Output is correct
7 Correct 262 ms 15444 KB Output is correct
8 Correct 123 ms 6548 KB Output is correct
9 Correct 88 ms 6348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Halted 0 ms 0 KB -