Submission #517811

#	Time	Username	Problem	Language	Result	Execution time	Memory
517811		blue	Arcade (NOI20_arcade)	C++17	100 / 100	916 ms	41704 KiB

Arcade

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

using pii = pair<int, int>;
using vi = vector<int>;
#define sz(x) int(x.size())

struct point
{
    int apt;
    int amt;
    int i;
};

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

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

    set<pii> S;
    int A[M], T[M];
    for(int i = 0; i < M; i++)
    {
        cin >> T[i];
    }

    for(int i = 0; i < M; i++)
    {
        cin >> A[i];
        S.insert({A[i], T[i]});
    }


    int Z = sz(S);

    vector<point> P(Z);

    for(int i = 0; i < Z; i++)
    {
        P[i].apt = S.begin()->first + S.begin()->second;
        P[i].amt = S.begin()->first - S.begin()->second;

        S.erase(S.begin());
    }

    sort(P.begin(), P.end(), [] (point u, point v)
    {
        if(u.apt != v.apt) return u.apt < v.apt;
        else return u.amt > v.amt;
    });
    for(int i = 0; i < Z; i++) P[i].i = i+1;

    int ans = 0;
    vi BIT(1+Z, 0);

    sort(P.begin(), P.end(), [] (point u, point v)
    {
        if(u.amt == v.amt) return u.apt > v.apt;
        return u.amt < v.amt;
    });

    for(point p: P)
    {
        int h = 1;
        for(int j = p.i-1; j >= 1; j -= j&-j)
            h = max(h, BIT[j]+1);

        ans = max(ans, h);

        for(int j = p.i; j <= Z; j += j&-j)
            BIT[j] = max(BIT[j], h);
    }

    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