53592023-04-26 13:46:30ZsofiaKeresztelySzakaszokcpp14Időlimit túllépés 79/100204ms31324 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ÖsszpontTesztVerdiktIdőMemória
base79/100
1Elfogadva0/03ms1852 KiB
2Elfogadva0/041ms4888 KiB
3Elfogadva2/23ms2952 KiB
4Elfogadva2/26ms3328 KiB
5Elfogadva2/28ms3676 KiB
6Elfogadva3/318ms4704 KiB
7Elfogadva3/310ms4632 KiB
8Elfogadva3/330ms5960 KiB
9Elfogadva3/332ms6548 KiB
10Elfogadva4/432ms7200 KiB
11Elfogadva4/439ms8084 KiB
12Elfogadva4/459ms10160 KiB
13Elfogadva7/781ms12700 KiB
14Elfogadva7/7101ms14764 KiB
15Elfogadva7/7126ms17048 KiB
16Időlimit túllépés0/7157ms17672 KiB
17Elfogadva7/767ms16780 KiB
18Elfogadva7/7123ms21632 KiB
19Elfogadva7/7140ms23980 KiB
20Időlimit túllépés0/7204ms29924 KiB
21Időlimit túllépés0/7156ms25244 KiB
22Elfogadva7/7123ms31324 KiB