oj.uz

답안 #106766

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106766 2019-04-20T11:02:05 Z FiloSanza Exhibition (JOI19_ho_t2) C++14
0 / 100
 2 ms 512 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){
        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 = upper_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:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<p.size(); i++){
                  ~^~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -