1402 2022. 09. 01 17:00:13 Valaki2 Szakaszok cpp14 Elfogadva 100/100 123ms 19340 KiB
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")

#define pb push_back

const int inf = 1e9 + 42;
const int maxn = 3e5 + 42;
int tree[1 + maxn];

struct fentree {

    int n;

    void update(int idx, int val) {
        while(idx <= maxn) {
            tree[idx] += val;
            idx += idx & (-idx);
        }
    }

    int pref_query(int idx) {
        int res = 0;
        while(idx > 0) {
            res += tree[idx];
            idx -= idx & (-idx);
        }
        return res;
    }

    int query(int ql, int qr) {
        return pref_query(qr) - pref_query(ql - 1);
    }

    fentree() : n(0) {}
    fentree(int n_) : n(n_) {}

};

struct event {
    int type, x, y, y1, y2, id;
    bool operator < (const event &other) const {
        if(x == other.x) {
            return type < other.type;
        }
        return x < other.x;
    }
};

vector<event> events;
vector<int> compress;

void solve() {
    int m, n;
    cin >> m >> n;
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        compress.pb(b);
        compress.pb(c);
        events.pb({1, a, c, -inf, -inf, i});
        events.pb({3, b, c, -inf, -inf, i});
    }
    for(int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        events.pb({2, a, -inf, b, c, i});
        compress.pb(b);
        compress.pb(c);
    }
    sort(events.begin(), events.end());
    sort(compress.begin(), compress.end());
    compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
    for(event &e : events) {
        if(e.y != -inf) {
            e.y = (lower_bound(compress.begin(), compress.end(), e.y) - compress.begin()) + 1;
        }
        if(e.y1 != -inf) {
            e.y1 = (lower_bound(compress.begin(), compress.end(), e.y1) - compress.begin()) + 1;
        }
        if(e.y2 != -inf) {
            e.y2 = (lower_bound(compress.begin(), compress.end(), e.y2) - compress.begin()) + 1;
        }
    }
    fentree my_tree(maxn);
    int ans = -1, best_cnt = 0;
    for(const event &e : events) {
        //cout << e.type << " " << e.x << " " << e.y << " " << e.y1 << " " << e.y2 << "\n";
        if(e.type == 1) {
            my_tree.update(e.y, 1);
        } else if(e.type == 2) {
            int cnt = my_tree.query(e.y1, e.y2);
            if(cnt > best_cnt) {
                best_cnt = cnt;
                ans = e.id;
            } else if(cnt == best_cnt && ans > e.id) {
                ans = e.id;
            }
        } else {
            my_tree.update(e.y, -1);
        }
    }
    cout << ans + 1 << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 2056 KiB
2 Elfogadva 0/0 24ms 4632 KiB
3 Elfogadva 2/2 2ms 2604 KiB
4 Elfogadva 2/2 4ms 3048 KiB
5 Elfogadva 2/2 4ms 3480 KiB
6 Elfogadva 3/3 10ms 4144 KiB
7 Elfogadva 3/3 7ms 3932 KiB
8 Elfogadva 3/3 17ms 4992 KiB
9 Elfogadva 3/3 18ms 5348 KiB
10 Elfogadva 4/4 18ms 5024 KiB
11 Elfogadva 4/4 24ms 5828 KiB
12 Elfogadva 4/4 37ms 7324 KiB
13 Elfogadva 7/7 45ms 7752 KiB
14 Elfogadva 7/7 54ms 8540 KiB
15 Elfogadva 7/7 65ms 11228 KiB
16 Elfogadva 7/7 123ms 18804 KiB
17 Elfogadva 7/7 39ms 7284 KiB
18 Elfogadva 7/7 67ms 11492 KiB
19 Elfogadva 7/7 86ms 13228 KiB
20 Elfogadva 7/7 123ms 19232 KiB
21 Elfogadva 7/7 123ms 19284 KiB
22 Elfogadva 7/7 68ms 19340 KiB