Submission #124093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
124093	2019-07-02T14:09:58 Z	rajarshi_basu	Exhibition (JOI19_ho_t2)	C++14	100 / 100	354 ms	9324 KB

joi2019_ho_t2

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define vv vector
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int MAXN = 3000;
const int MAXK = 100+10;

int main(){
    int n,m;
    cin >> n >> m;
    vi frames;
    vv<ii> pics;
    FOR(i,n){
        int a,b;cin >> a >> b;
        pics.pb({a,b});
    }
    FOR(i,m){
        int a;cin >> a;
        frames.pb(a);
    }
    sort(pics.begin(), pics.end(),greater<ii>());
    sort(frames.begin(), frames.end(),greater<int>());
    set<ii,greater<ii> > s;
    int PTR = 0;
    FOR(i,n){
        s.insert({pics[i].ss,-i});
    }

    int ind = 0;
    int ctr = 0;
    int lst = 1e9+10;
    while(ind < n and PTR < m and !s.empty()){
        while(ind < n and pics[ind].ff > frames[PTR]){
            ii x = {pics[ind].ss,-ind};
            if(s.lower_bound(x) != s.end())s.erase(x);
            ind++;
        }
        if(ind >= n)break;
        // ======== //
        //cout << ind << " " << PTR << endl;
        while(!s.empty()){
            ii x = *s.begin();
            s.erase(s.begin());
            if(x.ff <= lst){
                lst = x.ff;
                ctr++;
                break;
            }
        }
        // ======== //
        PTR++;
    }
    cout << ctr << endl;
    return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	360 KB	Output is correct

Subtask #2
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	360 KB	Output is correct
20	Correct	4 ms	376 KB	Output is correct
21	Correct	4 ms	380 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	4 ms	376 KB	Output is correct
25	Correct	4 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct
27	Correct	5 ms	380 KB	Output is correct
28	Correct	5 ms	376 KB	Output is correct
29	Correct	6 ms	376 KB	Output is correct
30	Correct	5 ms	376 KB	Output is correct
31	Correct	5 ms	376 KB	Output is correct
32	Correct	4 ms	380 KB	Output is correct
33	Correct	3 ms	376 KB	Output is correct
34	Correct	4 ms	376 KB	Output is correct
35	Correct	3 ms	376 KB	Output is correct
36	Correct	5 ms	376 KB	Output is correct
37	Correct	5 ms	376 KB	Output is correct

Subtask #3
50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	360 KB	Output is correct
20	Correct	4 ms	376 KB	Output is correct
21	Correct	4 ms	380 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	4 ms	376 KB	Output is correct
25	Correct	4 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct
27	Correct	5 ms	380 KB	Output is correct
28	Correct	5 ms	376 KB	Output is correct
29	Correct	6 ms	376 KB	Output is correct
30	Correct	5 ms	376 KB	Output is correct
31	Correct	5 ms	376 KB	Output is correct
32	Correct	4 ms	380 KB	Output is correct
33	Correct	3 ms	376 KB	Output is correct
34	Correct	4 ms	376 KB	Output is correct
35	Correct	3 ms	376 KB	Output is correct
36	Correct	5 ms	376 KB	Output is correct
37	Correct	5 ms	376 KB	Output is correct
38	Correct	277 ms	9160 KB	Output is correct
39	Correct	272 ms	9064 KB	Output is correct
40	Correct	268 ms	9228 KB	Output is correct
41	Correct	278 ms	9140 KB	Output is correct
42	Correct	276 ms	9180 KB	Output is correct
43	Correct	280 ms	9096 KB	Output is correct
44	Correct	277 ms	9208 KB	Output is correct
45	Correct	295 ms	9196 KB	Output is correct
46	Correct	274 ms	9120 KB	Output is correct
47	Correct	304 ms	8684 KB	Output is correct
48	Correct	306 ms	8876 KB	Output is correct
49	Correct	222 ms	6888 KB	Output is correct
50	Correct	216 ms	6824 KB	Output is correct
51	Correct	345 ms	9060 KB	Output is correct
52	Correct	335 ms	9324 KB	Output is correct
53	Correct	324 ms	9068 KB	Output is correct
54	Correct	265 ms	9100 KB	Output is correct
55	Correct	276 ms	9100 KB	Output is correct
56	Correct	224 ms	7760 KB	Output is correct
57	Correct	84 ms	1780 KB	Output is correct
58	Correct	189 ms	7740 KB	Output is correct
59	Correct	251 ms	7820 KB	Output is correct
60	Correct	85 ms	1908 KB	Output is correct
61	Correct	153 ms	4180 KB	Output is correct
62	Correct	354 ms	9200 KB	Output is correct
63	Correct	309 ms	9068 KB	Output is correct
64	Correct	306 ms	9204 KB	Output is correct
65	Correct	306 ms	9196 KB	Output is correct
66	Correct	311 ms	9068 KB	Output is correct
67	Correct	313 ms	9192 KB	Output is correct
68	Correct	321 ms	9192 KB	Output is correct
69	Correct	316 ms	9196 KB	Output is correct
70	Correct	306 ms	9272 KB	Output is correct
71	Correct	301 ms	9064 KB	Output is correct
72	Correct	287 ms	9068 KB	Output is correct
73	Correct	282 ms	9064 KB	Output is correct

Submission #124093

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 40.0 / 40.0

Subtask #3 50.0 / 50.0

Subtask #1
10.0 / 10.0

Subtask #2
40.0 / 40.0

Subtask #3
50.0 / 50.0