Submission #784997

#	Time	Username	Problem	Language	Result	Execution time	Memory
784997		aykhn	Watching (JOI13_watching)	C++14	0 / 100	27 ms	436 KiB

watching

#include <bits/stdc++.h>

// author: aykhn

using namespace std;

typedef long long ll;

#define TC int t; cin >> t; while (t--) _();
#define OPT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define new int32_t
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define int ll
#define ins insert
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount

int n, p, q, sz = 1;
int a[2000], mark[2000];
pair<int, pii> b[2000];
set<pair<int, pii>> s;
int st[8100];

void reset()
{
    for (int i = 0; i <= sz; i++) st[i] = 0;
}

void make(int ind, int val, int l, int r, int x)
{
    if (l + 1 == r)
    {
        st[x] = val;
        return;
    }
    int mid = (l + r) >> 1;

    if (ind < mid) make(ind, val, l, mid, 2*x+1);
    else make(ind, val, mid, r, 2*x+2);
    st[x] = st[2*x+1] + st[2*x+2];
}

int get(int lx, int rx, int l, int r, int x)
{
    if (l >= rx || r <= lx) return 0;
    if (l >= lx && r <= rx) return st[x];
    int mid = (l + r) >> 1;

    return get(lx, rx, l, mid, 2*x+1) + get(lx, rx, mid, r, 2*x+2);
}

bool calc(int mid)
{
    for (int i = 0; i < n; i++)
    {
        make(i, 1, 0, sz, 0);
    }
    for (int i = 0; i < n; i++)
    {
        mark[i] = 0;
        b[i].se.se = upper_bound(a, a + n, a[i] + 2 * mid - 1) - a - 1;
        b[i].se.fi = i;
        b[i].fi = b[i].se.se - b[i].se.fi + 1;
        b[i].fi *= -1;
    }

    int Q = min(q, n);

    while (Q--)
    {
        int mx = -1;
        int id = -1;
        for (int i = 0; i < n; i++)
        {
            int x = get(b[i].se.fi, b[i].se.se, 0, sz, 0);
            if (x > mx)
            {
                mx = x;
                id = i;
            }
        }

        for (int i = b[id].se.fi; i <= b[id].se.se; i++)
        {
            mark[i] = 1;
            make(i, 0, 0, sz, 0);
        }
    }

    int last = -1;
    int cnt = 0;

    for (int i = 0; i < n; i++)
    {
        if (mark[i]) continue;
        if (last == -1)
        {
            cnt++;
            last = a[i];
        }
        else
        {
            if (a[i] - last + 1 > mid)
            {
                cnt++;
                last = a[i];
            }
        }
    }
    if (cnt <= p) return true;
    else return false;
}

new main()
{
    OPT
    cin >> n >> p >> q;

    while (sz < n) sz <<= 1;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    sort(a, a + n);

    int l = 1;
    int r = 1e18;

    while (l < r)
    {
        int mid = (l + r) >> 1;

        if (calc(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;
}

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50