Submission #786220

#	Time	Username	Problem	Language	Result	Execution time	Memory
786220		kebine	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	212 KiB

joi2019_ho_t2

# include <bits/stdc++.h>
# define int long long
# define vi vector<int>
# define pb push_back
# define pii pair<int, int>
# define fi first
# define se second
# define endl '\n'
# define jess ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int n, m, x[100005];
pii a[100005];

bool comp(pii a, pii b) {
    if(a.fi<b.fi) return 1;
    if(a.fi>b.fi) return 0;
    if(a.se<b.se) return 1;
    return 0;
}

void solve() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> a[i].fi >> a[i].se;
    }
    sort(a+1, a+n+1);
    for(int i=1; i<=m; i++) {
        cin >> x[i];
    }
    sort(x+1, x+m+1);
    vi v;
    for(int i=1; i<=m; i++) {
        int mni=1e9, idx;
        for(int j=1; j<=n; j++) {
            // cout << "aj wkw " << j << " : " << a[j].fi << " " << a[j].se << " " << mni << " " << x[i] << endl;
            if(a[j].fi <= x[i]) {
                if(a[j].se<=mni) {
                    mni=a[j].se;
                    idx=j;
                }
            } else break;
        }
        if(mni==1e9) continue;
        else {
            v.pb(mni);
            a[idx].se=1e9;
        }
    } 
    if(v.size()==0) {
        cout << 0 << endl;
        return;
    }
    vi ans;
    ans.pb(v.back());
    for(int i=1; i<v.size(); i++) {
        if(v[i]>=ans.back()) {
            ans.pb(v[i]);
        } else {
            int low=lower_bound(ans.begin(), ans.end(), v[i]) - ans.begin();
            ans[low]=v[i];
        }
    }
    cout << ans.size() << endl;
}
 
signed main() {
    solve();
}

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'void solve()':
joi2019_ho_t2.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=1; i<v.size(); i++) {
      |                  ~^~~~~~~~~

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