#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+1] >= val)
return query(low,mid,pos*2+1,val);
else
return query(mid+1,high,pos*2+2,val-seg[pos*2+1]);
}
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];
ar[i].second = I[i];
ar[i].first = O[i]*I[i]*2-I[i]*I[i];
ans=max(ans,ar[i].first);
v.push_back(I[i]);
}
return ans;
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);
// ll ans = 0;
set < ll > used;
rep(i,0,n)
{
ar[i].first*=-1;
update(0,n,0,mapper[ar[i].second]);
used.insert(ar[i].second);
ll peaki = ar[i].first*2;
if(seg[0] > K)
{
ll maxim = inverse[query(0,n,0,K)];
if(peaki > maxim)
peaki = maxim;
else
{
ll cand1 = *(used.lower_bound(peaki));
ll cand2 = *(used.upper_bound(peaki));
if(cand2 > maxim)
peaki = cand1;
else if(ar[i].first*cand1-cand1*cand1 >= ar[i].first*cand2-cand2*cand2)
peaki = cand1;
else
peaki = cand2;
}
// cout << peaki << endl;
ans = max(ans,4*ar[i].first*peaki-peaki*peaki);
}
}
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:70:9:
rep(i,0,v.size())
~~~~~~~~~~~~
cross.cpp:70:5: note: in expansion of macro 'rep'
rep(i,0,v.size())
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
