oj.uz

Submission #517805

# Submission time Handle Problem Language Result Execution time Memory
517805 2022-01-23T07:31:18 Z blue Arcade (NOI20_arcade) C++17
0 / 100
 1 ms 204 KB 
#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 >> A[i];
    }

    for(int i = 0; i < M; i++)
    {
        cin >> T[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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -