Submission #759929

#	Time	Username	Problem	Language	Result	Execution time	Memory
759929		ibm2006	Crosses on the Grid (FXCUP4_cross)	C++17	0 / 100	1 ms	340 KiB

cross

#include<bits/stdc++.h>
#include "cross.h"
using namespace std;
typedef long long int ll;
ll n,i,j,m,s,t,a[1100000],x,y,z,k,ind;
vector<ll> v;
pair<ll,ll> p[1100000];
ll area(ll x,ll y)
{
    return 2*x*y-x*x;
}
void upd(ll x)
{
    a[x]=a[x*2]+a[x*2+1];
    if(x==1)
        return;
    upd(x/2);
}
ll query(ll x,ll z)
{
   // printf("%lld %lld\n",x,z);
    if(x>=524288&&z<=a[x])
        return x-524288;
        else if(x>=524288)
            return -1;
    if(a[x*2+1]<=z)
        return query(x*2,z-a[x*2+1]);
    return query(x*2+1,z);
}
long long SelectCross(int K, std::vector<int> I, std::vector<int> O)
{
    n=I.size();
    for(i=1;i<=n;i++)
    p[i]={O[i-1],I[i-1]};
    sort(p+1,p+n+1);
    for(i=1;i<=n;i++)
    {
        v.push_back(I[i-1]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(i=n;i>=1;i--)
    {
        z=query(1,K-1);
        //printf("%lld ",z);
        if(z>=0)
        {//printf("%lld %lld\n",v[z],p[i].first);
        s=max(s,area(v[z],p[i].first));
        }
        ind=lower_bound(v.begin(),v.end(),p[i].second)-v.begin()+1;
       // printf("%lld\n",ind);
        a[ind+524287]++;
        upd((ind+524287)/2);
    }
    return s;
}
/*int main()
{
    scanf("%lld %lld",&n,&k);
    vector<int> I,O;
    I.resize(n);
    O.resize(n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld %lld",&I[i-1],&O[i-1]);
    }
    printf("%lld",SelectCross(k,I,O));
}
*/

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