Submission #151714

#	Time	Username	Problem	Language	Result	Execution time	Memory
151714		leduykhongngu	Crosses on the Grid (FXCUP4_cross)	C++17	0 / 100	2 ms	380 KiB

cross

#include <vector>
#include <map>
#include <algorithm>
#include <assert.h>
long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
    //i<o
    int n = I.size();
    std::vector< std::pair<int, int > > rectangles;
    for (int i = 0; i < n; ++i) 
        rectangles.push_back({O[i], I[i]});
    sort(rectangles.begin(), rectangles.end());
    //reverse(rectangles.begin(), rectangles.end());
    std::map< int, int > mymap;
    for (auto rec : rectangles) {
        ++mymap[rec.second];
    }
    int cnt = 0;
    auto it = mymap.rbegin();
    long long res = 0;
    int last = 1e9 + 5;
    for (auto rec : rectangles) {
        //delete rec
        --mymap[rec.second];
        if (rec.second >= last) --cnt;
        while (it != mymap.rend() && cnt < K) {
            cnt += it -> second;
            last = it -> first;
            ++it;
        }
        if (cnt >= K) {
            int Long = rec.first, Short = last;
            assert(Long >= Short);
            res = std::max(res, 1ll * Long * Long - 1ll * (Long - Short) * (Long - Short));
        }
    }
    return res;
}

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