#include "cross.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#define ll long long
#define pi pair < ll,ll >
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXN 300004
using namespace std;
pi ar[MAXN];
ll seg[4*MAXN];
map < ll,ll > mapper;
map < ll,ll > inverse;
ll cnt = 1;
void update(ll low,ll high,ll pos,ll slow)
{
if(low == high && low == slow)
{
seg[pos]++;
return;
}
if(low > slow || high < slow)
return;
ll mid = (low+high)/2;
update(low,mid,pos*2+1,slow);
update(mid+1,high,pos*2+2,slow);
seg[pos] = seg[pos*2+1]+seg[pos*2+2];
return;
}
ll query(ll low,ll high,ll pos,ll val)
{
ll mid = (low+high)/2;
if(low == high)
return low;
if(seg[pos*2+2] >= val)
return query(mid+1,high,pos*2+2,val);
else
return query(low,mid,pos*2+1,val-seg[pos*2+2]);
}
ll findclosestright(ll low,ll high,ll pos,ll slow)
{
if(seg[pos] == 0)
return MAXN;
ll mid= (low+high)/2;
if(low > slow)
{
if(low == high)
return low;
else if(seg[pos*2+1] > 0)
return query(low,mid,pos*2+1,slow);
else
return query(mid+1,high,pos*2+2,slow);
}
if(high <= slow)
return MAXN;
return min(query(low,mid,pos*2+1,slow),query(mid+1,high,pos*2+2,slow));
}
ll findclosestleft(ll low,ll high,ll pos,ll shigh)
{
if(seg[pos] == 0)
return MAXN;
ll mid= (low+high)/2;
if(high <= shigh)
{
if(low == high)
return low;
else if(seg[pos*2+2] > 0)
return query(mid+1,high,pos*2+2,shigh);
else
return query(low,mid,pos*2+1,shigh);
}
if(low > shigh)
return -1;
return max(query(low,mid,pos*2+1,shigh),query(mid+1,high,pos*2+2,shigh));
}
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
int n = I.size();
vector < ll > v;
ll ans =0;
rep(i,0,n)
{
ar[i].first = -O[i]*1LL;
ar[i].second = I[i]*1LL;
v.push_back(I[i]);
v.push_back(O[i]);
}
sort(v.begin(),v.end());
rep(i,0,v.size())
{
if(!mapper[v[i]])
{
mapper[v[i]]= cnt;
inverse[cnt] = v[i];
cnt++;
}
}
sort(ar,ar+n);
rep(i,0,n)
{
ar[i].first*=-1;
update(0,n,0,mapper[ar[i].second]);
ll peaki = mapper[ar[i].first];
ll epilogi = 0;
if(seg[0] > K)
{
ll maxim = query(0,n,0,K);
ll cand1 = findclosestright(0,n,0,peaki);
ll cand2 = findclosestleft(0,n,0,peaki);
if(cand1 == -1)
cand1 = cand2;
else if(cand2 == MAXN)
cand2 = cand1;
if(cand2 > maxim)
epilogi = maxim;
else if(cand1 != -1 && cand1 > maxim)
epilogi = cand1;
else if(2*ar[i].first*inverse[cand1] - inverse[cand1]*inverse[cand1] <= 2*ar[i].first*inverse[cand2] - inverse[cand2]*inverse[cand2])
epilogi = cand2;
else
epilogi = cand1;
epilogi = inverse[epilogi];
// cout << ar[i].first << " " << epilogi << " " << maxim << " "<< inverse[maxim] << endl;
ans = max(ans,2*ar[i].first*epilogi - epilogi*epilogi);
}
}
return ans;
}
Compilation message
cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:9:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,a,b) for(int i = a;i < b;i++)
cross.cpp:113:9:
rep(i,0,v.size())
~~~~~~~~~~~~
cross.cpp:113:5: note: in expansion of macro 'rep'
rep(i,0,v.size())
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
