5360 2023. 04. 26 13:47:58 ZsofiaKeresztely Szakaszok cpp14 Elfogadva 100/100 141ms 15712 KiB
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
typedef long long ll;
vector<int> seg, cop;

int cc(int k){
    return lower_bound(cop.begin(), cop.end(), k) - cop.begin() + 1;
}

void upd(int v, int tl, int tr, int pos, int val){
    seg[v] += val;
    if (tl == tr) return;
    int tm = (tl + tr) / 2;
    if (tm >= pos) upd(2*v, tl, tm, pos, val);
    else upd(2*v+1, tm+1, tr, pos, val);
}

int query(int v, int tl, int tr, int l, int r){
    if (r < l) return 0;
    if (tl == l && tr == r) return seg[v];
    int tm = (tl + tr) / 2;
    return query(2*v, tl, tm, l, min(tm, r)) + query(2*v+1, tm+1, tr, max(tm+1, l), r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<pair<pii, pii> > q;
    for (int i=0; i<n; i++){
        int x1, x2, y;
        cin >> x1 >> x2 >> y;
        q.push_back({{x1, 0}, {y, 1}});
        q.push_back({{x2, 1e9}, {y, -1}});
        cop.push_back(y);
    }
    for (int i=0; i<m; i++){
        int x, y1, y2;
        cin >> x >> y1 >> y2;
        q.push_back({{x, i+1}, {y1, y2}});
        cop.push_back(y1);
        cop.push_back(y2);
    }
    sort(q.begin(), q.end());
    sort(cop.begin(), cop.end());
    cop.erase(unique(cop.begin(), cop.end()), cop.end());
    seg.assign(4*cop.size(), 0);
    pii maxi = {0, 0};
    for (auto cur : q){
        if (cur.fi.se && cur.fi.se < 1e9){
            int val = query(1, 1, cop.size(), cc(cur.se.fi), cc(cur.se.se));
            maxi = min(maxi, {val*-1, cur.fi.se});
        }
        else{
            upd(1, 1, cop.size(), cc(cur.se.fi), cur.se.se);
        }
    }
    cout << maxi.se;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 1832 KiB
2 Elfogadva 0/0 27ms 4116 KiB
3 Elfogadva 2/2 3ms 2012 KiB
4 Elfogadva 2/2 4ms 2576 KiB
5 Elfogadva 2/2 6ms 2840 KiB
6 Elfogadva 3/3 13ms 3560 KiB
7 Elfogadva 3/3 7ms 3436 KiB
8 Elfogadva 3/3 20ms 4548 KiB
9 Elfogadva 3/3 21ms 4760 KiB
10 Elfogadva 4/4 21ms 4736 KiB
11 Elfogadva 4/4 27ms 5000 KiB
12 Elfogadva 4/4 39ms 6632 KiB
13 Elfogadva 7/7 56ms 8420 KiB
14 Elfogadva 7/7 70ms 9500 KiB
15 Elfogadva 7/7 83ms 10756 KiB
16 Elfogadva 7/7 140ms 15664 KiB
17 Elfogadva 7/7 45ms 7236 KiB
18 Elfogadva 7/7 83ms 10628 KiB
19 Elfogadva 7/7 93ms 11424 KiB
20 Elfogadva 7/7 141ms 15460 KiB
21 Elfogadva 7/7 140ms 15712 KiB
22 Elfogadva 7/7 71ms 14024 KiB