oj.uz

Submission #759929

# Submission time Handle Problem Language Result Execution time Memory
759929 2023-06-17T05:24:49 Z ibm2006 Crosses on the Grid (FXCUP4_cross) C++17
0 / 100
 1 ms 340 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -