oj.uz

Submission #149290

# Submission time Handle Problem Language Result Execution time Memory
149290 2019-09-01T06:09:21 Z Dopatii(#3751, bogdan10bos, Gioto, Bodo171) Crosses on the Grid (FXCUP4_cross) C++17
100 / 100
 548 ms 26280 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;
    }
};struct elem2{
    int x, y;

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

elem a[200005];
elem2 b[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(n) - 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]};
        b[i] = {I[i - 1], O[i - 1]};
	}

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

    for(int i = 1; i <= N ; ++i) f[b[i].y] = i, f2[i] = b[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 5 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 26 ms 1920 KB Output is correct
6 Correct 511 ms 26220 KB Output is correct
7 Correct 505 ms 26216 KB Output is correct
8 Correct 548 ms 26212 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 26 ms 1920 KB Output is correct
6 Correct 511 ms 26220 KB Output is correct
7 Correct 505 ms 26216 KB Output is correct
8 Correct 548 ms 26212 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 26 ms 1920 KB Output is correct
13 Correct 232 ms 13644 KB Output is correct
14 Correct 502 ms 26212 KB Output is correct
15 Correct 531 ms 26216 KB Output is correct
16 Correct 548 ms 26280 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 26 ms 1920 KB Output is correct
6 Correct 511 ms 26220 KB Output is correct
7 Correct 505 ms 26216 KB Output is correct
8 Correct 548 ms 26212 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 26 ms 1920 KB Output is correct
13 Correct 232 ms 13644 KB Output is correct
14 Correct 502 ms 26212 KB Output is correct
15 Correct 531 ms 26216 KB Output is correct
16 Correct 548 ms 26280 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 7 ms 512 KB Output is correct
19 Correct 22 ms 2048 KB Output is correct
20 Correct 235 ms 13548 KB Output is correct
21 Correct 408 ms 20844 KB Output is correct
22 Correct 489 ms 26212 KB Output is correct
23 Correct 451 ms 26216 KB Output is correct
24 Correct 482 ms 26212 KB Output is correct
25 Correct 403 ms 26216 KB Output is correct
26 Correct 407 ms 26220 KB Output is correct