oj.uz

Submission #149267

# Submission time Handle Problem Language Result Execution time Memory
149267 2019-09-01T06:06:08 Z Dopatii(#3751, bogdan10bos, Gioto, Bodo171) Crosses on the Grid (FXCUP4_cross) C++17
8 / 100
 652 ms 24684 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 23 ms 1920 KB Output is correct
6 Correct 652 ms 24684 KB Output is correct
7 Correct 515 ms 24424 KB Output is correct
8 Correct 522 ms 24684 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 23 ms 1920 KB Output is correct
6 Correct 652 ms 24684 KB Output is correct
7 Correct 515 ms 24424 KB Output is correct
8 Correct 522 ms 24684 KB Output is correct
9 Incorrect 6 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 23 ms 1920 KB Output is correct
6 Correct 652 ms 24684 KB Output is correct
7 Correct 515 ms 24424 KB Output is correct
8 Correct 522 ms 24684 KB Output is correct
9 Incorrect 6 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -