#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
//consider the case where we only need k smallest from two different set of points
//if can do this in some reasonable time then apply zs bit trick
//+log factor
//need <= log^3 maybe?
//ok two set need log^2(?)
#define all(a) a.begin(),a.end()
#define pb push_back
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
const int MAXN = 2000000;
vector<ll>glo;
multiset<int>fen[MAXN];
multiset<int>::iterator it[MAXN];
vector<int>touch;
void upd(int i,int n,int v){
for(;i<=n;i+=i&(-i))fen[i].insert(v);
}
void query(int i){
while(i>0){
touch.pb(i);
i-=i&(-i);
}
}
#define fi first
#define se second
typedef pair<int,int> pii;
int main()
{
owo
int n,k;
cin>>n>>k;
vector<array<int,2>>p(n);
vector<int>cy(n);
for(int i=0;i<n;i++)cin>>p[i][0]>>p[i][1];
sort(all(p));
vector<int>crd;
for(int i=0;i<n;i++)crd.push_back(p[i][1]);
sort(all(crd));
crd.resize(unique(all(crd)) - crd.begin());
for(int i=0;i<n;i++)cy[i] = lower_bound(all(crd),p[i][1]) - crd.begin()+1;
int m = crd.size();
if(k==1){
ll ans = 1e18;
for(int i=0;i<n;i++){
touch.clear();
query(cy[i]);
int s = touch.size();
for(int j=0;j<s;j++){
if(fen[touch[j]].empty())continue;
ll c = p[i][0] + p[i][1];
c-=*fen[touch[j]].begin();
ans = min(ans,c);
}
upd(cy[i],m,p[i][0]+p[i][1]);
}
//cout<<ans<<'\n';
//y(i) < y(j) case
//we use x(i) - y(i) - (x(j)-y(j))
for(int i=1;i<=m;i++)fen[i].clear(); //i need to do the opposite directly
for(int i=0;i<n;i++){
touch.clear();
cy[i] = m-cy[i]+1;
query(cy[i]-1);
int s = touch.size();
for(int j=0;j<s;j++){
if(fen[touch[j]].empty())continue;
ll c = p[i][0] - p[i][1];
c-=*fen[touch[j]].begin();
ans = min(ans,c);
}
upd(cy[i],m,p[i][0]-p[i][1]);
}
cout<<ans<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
109864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
116960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3591 ms |
220536 KB |
Output is correct |
| 2 |
Incorrect |
3508 ms |
225764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3591 ms |
220536 KB |
Output is correct |
| 2 |
Incorrect |
3508 ms |
225764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
109864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
109864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
