Submission #517447

#	Time	Username	Problem	Language	Result	Execution time	Memory
517447		blue	Arcade (NOI20_arcade)	C++17	100 / 100	847 ms	51052 KiB

Arcade

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct point
{
    int A;
    int T;
};

bool operator < (point A, point B)
{
    if(A.T == B.T) return A.A < B.A;
    return A.T < B.T;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    point P[M];
    for(int i = 0; i < M; i++) cin >> P[i].T;
    for(int i = 0; i < M; i++) cin >> P[i].A;

    sort(P, P+M, [] (point u, point v)
    {
        return u.A < v.A;
    });

    set<point> hands[M]; //first = time, second = loc

    int occ = -1;

    for(point p: P)
    {
        // cerr << "point: " << p.A << ' ' << p.T << '\n';
        int lo = 0, hi = min(M-1, occ+1);
        while(lo != hi)
        {
            int mid = (lo+hi)/2;

            bool lw = 0, rw = 0;

            auto f = hands[mid].lower_bound({-1, p.T});
            if(f == hands[mid].end()) rw = 1;
            else
            {
                if(abs(f->A - p.A) <= f->T - p.T) rw = 1;
            }

            if(f == hands[mid].begin())
                lw = 1;
            else
            {
                f--;
                if(abs(f->A - p.A) <= p.T - f->T) lw = 1;
            }

            if(lw && rw)
                hi = mid;
            else
                lo = mid+1;
        }

        // cerr << "inserted into " << lo << '\n';

        hands[lo].insert(p);
        occ = max(occ, lo);
    }

    int ans = 0;
    for(int i = 0; i < M; i++) ans += !(hands[i].empty());

    cout << ans << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 14 / 14
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15