#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int, int> pii;
const int MAX_N = 200000;
int N;
deque<pii> dq1, dq2;
vector<int> cnt[MAX_N+1];
int idx[MAX_N+1];
int ans;
set<pii> st;
struct SEG{
SEG (int sum, int l, int r) : sum(sum), l(l), r(r) {}
int sum;
int l, r;
};
vector<SEG> seg;
void init(int idx, int s, int e){
seg.push_back({0, -1, -1});
if(s==e) return;
seg[idx].l=seg.size(); init(seg[idx].l, s, (s+e)/2);
seg[idx].r = seg.size(); init(seg[idx].r, (s+e)/2+1, e);
}
void update(int idx, int s, int e, int x, int y){
seg[idx].sum+=y;
if(s==e) return;
if(x<=(s+e)/2) update(seg[idx].l, s, (s+e)/2, x, y);
else update(seg[idx].r, (s+e)/2+1, e, x, y);
}
int sum(int idx, int s, int e, int x, int y){
if(x<=s && e<=y) return seg[idx].sum;
if(x>e || y<s) return 0;
return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
}
bool able(int x, int k){
int y = cnt[x].back();
//cout<<x<<' '<<y<<endl;
auto it = st.upper_bound({y, 2*N});
it--;
pii now = (*it);
//cout<<now.F<<' '<<now.S<<endl;
if(now.F<=idx[k] && now.S>=N-k){
return true;
}
if(sum(0, 0, N-1, now.first, N-1)-1>=now.second){
return true;
}return false;
}
int main(){
scanf("%d", &N);
init(0, 0, N-1); for(int i=0; i<N; i++) update(0, 0, N-1, i, 1);
ans = N;
for(int i=0; i<N; i++){
int a, b; scanf("%d%d", &a, &b);
dq1.push_back({a, b});
}for(int i=0; i<N; i++){
int a, b; scanf("%d%d", &a, &b);
dq2.push_back({a, b});
}
for(int i=0; i<N; i++){
if(i==0) idx[i] = 0;
else idx[i] = idx[i-1];
while(dq1[idx[i]].second > dq2[i].second){
idx[i]++;
}
st.insert({idx[i], N-i});
}
for(int i=N-1; i>=0; i--){
cnt[dq1[i].F].push_back(i);
}
for(int i=0; i<N; i++){
pii now = dq2[i];
while(!dq1.empty() && dq1.front().S > now.S){
if(!cnt[dq1.front().F].empty() && (cnt[dq1.front().F].back()==N-dq1.size())){
cnt[dq1.front().F].pop_back();
}
dq1.pop_front();
}
while(!cnt[now.F].empty()){
if(able(now.F, i)){
//cout<<'*'<<cnt[now.F].back()<<endl;
update(0, 0, N-1, cnt[now.F].back(), -1);
cnt[now.F].pop_back();
ans--; break;
}else cnt[now.F].pop_back();
}
}
printf("%d", ans);
return 0;
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:85:64: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(!cnt[dq1.front().F].empty() && (cnt[dq1.front().F].back()==N-dq1.size())){
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
worst_reporter2.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
worst_reporter2.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |