Submission #150741

#	Time	Username	Problem	Language	Result	Execution time	Memory
150741		(παρα)γεμιστά (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	100 / 100	932 ms	50024 KiB

cross

#include "cross.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define ll long long
#define pi pair < ll,ll >
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXN 2000004

using namespace std;

pi ar[MAXN];
ll seg[4*MAXN];
unordered_map < ll,ll > mapper;
unordered_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 findclosestright(low,mid,pos*2+1,slow);
        else
            return findclosestright(mid+1,high,pos*2+2,slow);
    }
    if(high <= slow)
        return MAXN;

    return min(findclosestright(low,mid,pos*2+1,slow),findclosestright(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 findclosestleft(mid+1,high,pos*2+2,shigh);
        else
            return findclosestleft(low,mid,pos*2+1,shigh);
    }
    if(low > shigh)
        return -1;

    return max(findclosestleft(low,mid,pos*2+1,shigh),findclosestleft(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,cnt,0,mapper[ar[i].second]);
        ll peaki = mapper[ar[i].first];
        ll epilogi = 0;

        if(seg[0] >= K)
        {
            ll maxim = query(0,cnt,0,K);
            ll cand2 = findclosestright(0,cnt,0,peaki);
            ll cand1 = findclosestleft(0,cnt,0,peaki);

            if(cand1 == -1)
                cand1 = cand2;
            else if(cand2 == MAXN)
                cand2 = cand1;

            if(cand1 > maxim)
                epilogi = maxim;
            else if(cand1 != -1 && cand2 > 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];

            ans = max(ans,2*ar[i].first*epilogi - epilogi*epilogi);
        }
    }

	return ans;
}

Compilation message (stderr)

cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:8: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())
     ^~~

• Subtask 1: 8 / 8
• Subtask 2: 55 / 55
• Subtask 3: 37 / 37