#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int n,q,vasps[maxn],vassuf[maxn];
pair<int,int>all[maxn];
vector<int>fps,fsuf;
void vorod(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>all[i].first>>all[i].second;
}
}
void pre(){
set<pair<int,int>>st;
int now=0;
while(true){
int nx=now;
if((int)st.size()>0){
nx=max(nx,(*st.rbegin()).first);
}
if(nx==now){
vasps[now]=1;
st.insert(make_pair(all[now+1].second,now+1));
}else{
fps.push_back((*st.rbegin()).second);
st.clear();
for(int i=now+1;i<=nx;i++){
st.insert(make_pair(all[i].second,i));
}
now=nx;
}
if(now==n){
break;
}
}
st.clear();
now=n+1;
while(true){
int nx=now;
if((int)st.size()>0){
nx=min(nx,(*st.begin()).first);
}
if(nx==now){
vassuf[now]=1;
st.insert(make_pair(all[now-1].first,now-1));
}else{
fsuf.push_back((*st.rbegin()).second);
st.clear();
for(int i=now-1;i>=nx;i--){
st.insert(make_pair(all[i].first,i));
}
now=nx;
}
if(now==1){
break;
}
}
for(int i=1;i<=n;i++){
vassuf[i]|=vassuf[i-1];
}
for(int i=n;i>=1;i--){
vasps[i]|=vasps[i+1];
}
}
void khor(){
int q;
cin>>q;
int x;
cin>>x;
if(x!=1||q!=1){
assert(0);
}
if(vasps[1]==0){
cout<<fps.size()<<"\n";
}else{
cout<<-1<<"\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("inp.txt","r",stdin);
vorod();
pre();
khor();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2516 KB |
Output is correct |
3 |
Correct |
2 ms |
2396 KB |
Output is correct |
4 |
Correct |
119 ms |
14956 KB |
Output is correct |
5 |
Correct |
48 ms |
6228 KB |
Output is correct |
6 |
Correct |
39 ms |
7772 KB |
Output is correct |
7 |
Correct |
73 ms |
14312 KB |
Output is correct |
8 |
Correct |
54 ms |
8532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Runtime error |
3 ms |
4764 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Runtime error |
3 ms |
4764 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Runtime error |
3 ms |
4764 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2516 KB |
Output is correct |
3 |
Correct |
2 ms |
2396 KB |
Output is correct |
4 |
Correct |
119 ms |
14956 KB |
Output is correct |
5 |
Correct |
48 ms |
6228 KB |
Output is correct |
6 |
Correct |
39 ms |
7772 KB |
Output is correct |
7 |
Correct |
73 ms |
14312 KB |
Output is correct |
8 |
Correct |
54 ms |
8532 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Runtime error |
3 ms |
4764 KB |
Execution killed with signal 6 |
11 |
Halted |
0 ms |
0 KB |
- |