oj.uz

Submission #106786

# Submission time Handle Problem Language Result Execution time Memory
106786 2019-04-20T13:07:48 Z FiloSanza Exhibition (JOI19_ho_t2) C++14
0 / 100
 2 ms 384 KB 
#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){
        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){
        return a.v < b.v;
    });

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

    if(p.size() == 0){
        cout << 0;
        return 0;
    }

    //LIS
    vector<int> sol;
    sol.push_back(p[0]);
    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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -