Submission #149267

#	Time	Username	Problem	Language	Result	Execution time	Memory
149267		Dopatii (#200)	Crosses on the Grid (FXCUP4_cross)	C++17	8 / 100	652 ms	24684 KiB

cross

#include "cross.h"
#include <bits/stdc++.h>
using namespace std;

struct elem{
    int x, y;

    bool operator < (const elem &aux)const{
        if(x != aux.x) return x > aux.x;
        return y < aux.y;
    }

};

elem a[200005];

int n;
int aib[200005];
map <int, int> f, f2;

void u(int x, int v){
    for(int i = x; i <= n ; i = i + (i & (-i))) aib[i] += v;
}

int q(int x){
    int ans = 0;
    for(int i = x; i >= 1 ; i = i - (i & (-i))) ans += aib[i];
    return ans;
}

int kth(int k){
    int st = 1, dr = n;
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(q(dr) - q(mij - 1) < k) dr = mij - 1;
        else st = mij + 1;
    }

    return f2[dr];
}


long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int N = I.size();
    n = N;

	for(int i = 1; i <= N ; ++i){
        a[i] = {I[i - 1], O[i - 1]};
	}

	sort(a + 1, a + N + 1);

    for(int i = 1; i <= N ; ++i) f[a[i].y] = i, f2[i] = a[i].y;

    for(int i = 1; i < K ; ++i) u(f[a[i].y], 1);

    long long Sol = 0;
    for(int i = K; i <= N ; ++i){
        u(f[a[i].y], 1);

        int X = a[i].x;
        int Y = kth(K);

        Sol = max(Sol, 2LL * X * Y - 1LL * X * X);
    }

	return Sol;
}

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