5359 2023. 04. 26 13:46:30 ZsofiaKeresztely Szakaszok cpp14 Időlimit túllépés 79/100 204ms 31324 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()
{
    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 79/100
1 Elfogadva 0/0 3ms 1852 KiB
2 Elfogadva 0/0 41ms 4888 KiB
3 Elfogadva 2/2 3ms 2952 KiB
4 Elfogadva 2/2 6ms 3328 KiB
5 Elfogadva 2/2 8ms 3676 KiB
6 Elfogadva 3/3 18ms 4704 KiB
7 Elfogadva 3/3 10ms 4632 KiB
8 Elfogadva 3/3 30ms 5960 KiB
9 Elfogadva 3/3 32ms 6548 KiB
10 Elfogadva 4/4 32ms 7200 KiB
11 Elfogadva 4/4 39ms 8084 KiB
12 Elfogadva 4/4 59ms 10160 KiB
13 Elfogadva 7/7 81ms 12700 KiB
14 Elfogadva 7/7 101ms 14764 KiB
15 Elfogadva 7/7 126ms 17048 KiB
16 Időlimit túllépés 0/7 157ms 17672 KiB
17 Elfogadva 7/7 67ms 16780 KiB
18 Elfogadva 7/7 123ms 21632 KiB
19 Elfogadva 7/7 140ms 23980 KiB
20 Időlimit túllépés 0/7 204ms 29924 KiB
21 Időlimit túllépés 0/7 156ms 25244 KiB
22 Elfogadva 7/7 123ms 31324 KiB