// Super Idol的笑容
// 都没你的甜
// 八月正午的阳光
// 都没你耀眼
// 热爱105°C的你
// 滴滴清纯的蒸馏水
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m,k;
ii arr[200005];
ii brr[200005];
bool dir[200005];
set<ii,greater<ii> > l,r;
void rem(int i){
l.erase({brr[i].fi,i});
r.erase({brr[i].se,i});
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>m>>k;
rep(x,1,k+1) cin>>arr[x].fi>>arr[x].se;
vector<int> idx;
rep(x,1,k+1) idx.pub(x);
sort(all(idx),[](int i,int j){
if (arr[i].fi!=arr[j].fi) return arr[i].fi<arr[j].fi;
else return arr[i].se>arr[j].se;
});
rep(x,0,k) brr[idx[x]].fi=x;
sort(all(idx),[](int i,int j){
if (arr[i].se!=arr[j].se) return arr[i].se<arr[j].se;
else return arr[i].fi>arr[j].fi;
});
rep(x,0,k) brr[idx[x]].se=x;
rep(x,1,k+1) l.insert({brr[x].fi,x});
rep(x,1,k+1) r.insert({brr[x].se,x});
int ans=n+m;
while (!l.empty()){
if ((*l.begin()).se==(*r.begin()).se){
rem((*l.begin()).se);
}
else{
int a=(*l.begin()).se,b=(*r.begin()).se;
int lv2=arr[a].fi,rv2=arr[b].se;
int lv1=arr[b].fi,rv1=arr[a].se;
rem(a);
rem(b);
dir[b]=1;
while (!l.empty()){
a=(*l.begin()).se,b=(*r.begin()).se;
if (lv1<arr[a].fi){
rv1=min(rv1,arr[a].se);
rem(a);
}
else if (rv1<arr[b].se){
lv1=min(lv1,arr[b].fi);
rem(b);
dir[b]=1;
}
else break;
}
// cout<<lv1<<" "<<lv2<<endl;
// cout<<rv1<<" "<<rv2<<endl;
ans-=(lv2-lv1+1)+(rv2-rv1+1);
ans++;
}
}
cout<<ans<<endl;
rep(x,1,k+1) cout<<dir[x]<<" "; cout<<endl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:31:26: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
31 | #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
| ^~~
Main.cpp:118:2: note: in expansion of macro 'rep'
118 | rep(x,1,k+1) cout<<dir[x]<<" "; cout<<endl;
| ^~~
Main.cpp:118:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
118 | rep(x,1,k+1) cout<<dir[x]<<" "; cout<<endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
