Submission #106767

#	Time	Username	Problem	Language	Result	Execution time	Memory
106767		FiloSanza	Exhibition (JOI19_ho_t2)	C++14	0 / 100	3 ms	512 KiB

joi2019_ho_t2

#include <bits/stdc++.h>

using namespace std;

struct paint{
    int s, v, i, m = -1;
};

int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);

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

    vector<int> p;
    vector<int> f(M);
    vector<paint> v(N);
    for(int i=0; i<N; i++) v[i].i = i, cin >> v[i].s >> v[i].v;
    for(auto &i : f) cin >> i;

    sort(f.begin(), f.end());
    sort(v.begin(), v.end(), [](const paint& a, const paint& b){
        if(a.s == b.s)
            return a.i < b.i;
        return a.s < b.s;
    });
    
    for(int i=0, j=0; i<N && j<M; i++){
        while(j<M && f[j]<v[i].s) j++;
        if(j>=M) continue;
        v[i].m = j;
        j++;
    }

    sort(v.begin(), v.end(), [](const paint& a, const paint& b){
        if(a.v == b.v)
            return a.i < b.i;
        return a.v < b.v;
    });

    for(auto i : v) if(i.m != -1) p.push_back(i.m);

    //LIS
    vector<int> sol;
    sol.push_back(p.front());
    for(int i=1; i<p.size(); i++){
        if(p[i] < sol.front()) sol[0] = p[i];
        else if(p[i] > sol.back()) sol.push_back(p[i]);
        else{
            auto it = lower_bound(sol.begin(), sol.end(), p[i]);
            sol[it-sol.begin()] = p[i];
        }
    }

    cout << sol.size();
}

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<p.size(); i++){
                  ~^~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50