#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
const int inf = 1e18;
int n,m;
vector<pair<int,int> > paintings;
vector<int> frames;
bool check(int k){
H(k);
priority_queue<int> pq;
int j = 0;
int ma = 0;
for(int i = m-k; i<m; i++){
while(j<n && paintings[j].first <= frames[i]){
pq.push(-paintings[j++].second);
P('&');
}
while(!pq.empty() && -pq.top() < ma){
pq.pop();
P('b');
}
if(pq.empty()){
P('#');
return false;
}
ma = max(ma, -pq.top());
pq.pop();
}
return true;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
paintings.resize(n);
frames.resize(m);
F(i,n){
cin>>paintings[i].first>>paintings[i].second;
}
F(i,m){
cin>>frames[i];
}
sort(paintings.begin(),paintings.end());
sort(frames.begin(),frames.end());
int res = 0;
for(int bs = 1<<20; bs>0; bs/=2) if(res+bs <= m && check(res+bs)){
res+=bs;
}
cout<<res<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
3 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
1 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
3 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
2 ms |
384 KB |
Output is correct |
38 |
Correct |
84 ms |
6312 KB |
Output is correct |
39 |
Correct |
80 ms |
6264 KB |
Output is correct |
40 |
Correct |
97 ms |
6328 KB |
Output is correct |
41 |
Correct |
94 ms |
6264 KB |
Output is correct |
42 |
Correct |
60 ms |
5624 KB |
Output is correct |
43 |
Correct |
58 ms |
5624 KB |
Output is correct |
44 |
Correct |
182 ms |
7256 KB |
Output is correct |
45 |
Correct |
138 ms |
6772 KB |
Output is correct |
46 |
Correct |
116 ms |
6772 KB |
Output is correct |
47 |
Correct |
160 ms |
5904 KB |
Output is correct |
48 |
Correct |
129 ms |
5948 KB |
Output is correct |
49 |
Correct |
206 ms |
5468 KB |
Output is correct |
50 |
Correct |
158 ms |
5456 KB |
Output is correct |
51 |
Correct |
63 ms |
5624 KB |
Output is correct |
52 |
Correct |
59 ms |
5752 KB |
Output is correct |
53 |
Correct |
61 ms |
5612 KB |
Output is correct |
54 |
Correct |
104 ms |
7500 KB |
Output is correct |
55 |
Correct |
92 ms |
6264 KB |
Output is correct |
56 |
Correct |
37 ms |
4472 KB |
Output is correct |
57 |
Correct |
22 ms |
2160 KB |
Output is correct |
58 |
Correct |
39 ms |
5712 KB |
Output is correct |
59 |
Correct |
58 ms |
5732 KB |
Output is correct |
60 |
Correct |
22 ms |
2176 KB |
Output is correct |
61 |
Correct |
105 ms |
3832 KB |
Output is correct |
62 |
Correct |
258 ms |
7140 KB |
Output is correct |
63 |
Correct |
265 ms |
7136 KB |
Output is correct |
64 |
Correct |
258 ms |
7144 KB |
Output is correct |
65 |
Correct |
256 ms |
7140 KB |
Output is correct |
66 |
Correct |
261 ms |
7136 KB |
Output is correct |
67 |
Correct |
261 ms |
7268 KB |
Output is correct |
68 |
Correct |
265 ms |
7272 KB |
Output is correct |
69 |
Correct |
255 ms |
7140 KB |
Output is correct |
70 |
Correct |
266 ms |
7140 KB |
Output is correct |
71 |
Correct |
231 ms |
7136 KB |
Output is correct |
72 |
Correct |
217 ms |
7144 KB |
Output is correct |
73 |
Correct |
214 ms |
7124 KB |
Output is correct |