| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 149288 | (παρα)γεμιστά (#200) | Crosses on the Grid (FXCUP4_cross) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
ans=max(ans,O[i]*I[i]*4-I[i]*I[i]);
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;
}