13932022-08-31 14:05:00Valaki2Szakaszokcpp14Futási hiba 0/100166ms36848 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back

const int inf = 1e9 + 42;
const int maxn = 1e6;

struct segtree {

    int n;
    vector<int> tree;

    void build(const vector<int> &arr, int v, int vl, int vr) {
        if(vl == vr) {
            tree[v] = arr[vl];
        } else {
            int mid = (vl + vr) / 2;
            build(arr, 2 * v, vl, mid);
            build(arr, 2 * v + 1, mid + 1, vr);
            tree[v] = max(tree[2 * v], tree[2 * v + 1]);
        }
    }

    void update(int pos, int val, int v, int vl, int vr) {
        if(vl == vr) {
            tree[v] += val;
        } else {
            int mid = (vl + vr) / 2;
            if(pos <= mid) {
                update(pos, val, 2 * v, vl, mid);
            } else {
                update(pos, val, 2 * v + 1, mid + 1, vr);
            }
            tree[v] = max(tree[2 * v], tree[2 * v + 1]);
        }
    }

    int query(int ql, int qr, int v, int vl, int vr) {
        if(qr < vl || ql > vr) {
            return 0;
        }
        if(ql == vl && qr == vr) {
            return tree[v];
        } else {
            int mid = (vl + vr) / 2;
            return max(query(ql, min(qr, mid), 2 * v, vl, mid),
                query(max(ql, mid + 1), qr, 2 * v + 1, mid + 1, vr));
        }
    }

    segtree() : n(0), tree(0) {}
    segtree(int n_) : n(n_), tree(1 + 4 * n_, 0) {}
    segtree(int n_, const vector<int> &arr) : n(n_), tree(1 + 4 * n_, 0) {
        build(arr, 1, 1, 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;
    }
};

void solve() {
    int m, n;
    cin >> m >> n;
    vector<event> events;
    vector<int> compress;
    compress.pb(-inf);
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        compress.pb(a);
        compress.pb(b);
        compress.pb(c);
        events.pb({1, a, c, 0, 0, i});
        events.pb({3, b, c, 0, 0, i});
    }
    for(int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        events.pb({2, a, 0, b, c, i});
        compress.pb(a);
        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) {
        e.x = (lower_bound(compress.begin(), compress.end(), e.x) - compress.begin()) + 1;
        e.y = (lower_bound(compress.begin(), compress.end(), e.y) - compress.begin()) + 1;
        e.y1 = (lower_bound(compress.begin(), compress.end(), e.y1) - compress.begin()) + 1;
        e.y2 = (lower_bound(compress.begin(), compress.end(), e.y2) - compress.begin()) + 1;
    }
    segtree my_tree(maxn);
    int ans = -1, best_cnt = 0;
    //
    for(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, 1, 1, maxn);
        } else if(e.type == 2) {
            int cnt = my_tree.query(e.y1, e.y2, 1, 1, maxn);
            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, 1, 1, maxn);
        }
    }
    cout << ans + 1 << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/100
1Futási hiba0/04ms2524 KiB
2Futási hiba0/032ms7164 KiB
3Futási hiba0/24ms2896 KiB
4Futási hiba0/27ms3544 KiB
5Futási hiba0/28ms3980 KiB
6Futási hiba0/316ms5300 KiB
7Futási hiba0/39ms5188 KiB
8Futási hiba0/324ms7632 KiB
9Futási hiba0/325ms7456 KiB
10Futási hiba0/425ms7596 KiB
11Futási hiba0/432ms8344 KiB
12Futási hiba0/448ms11948 KiB
13Futási hiba0/757ms12760 KiB
14Futási hiba0/771ms14936 KiB
15Futási hiba0/786ms20836 KiB
16Időlimit túllépés0/7165ms19508 KiB
17Futási hiba0/750ms12568 KiB
18Futási hiba0/786ms20800 KiB
19Futási hiba0/7115ms22944 KiB
20Időlimit túllépés0/7166ms19712 KiB
21Időlimit túllépés0/7163ms19836 KiB
22Futási hiba0/797ms36848 KiB