53602023-04-26 13:47:58ZsofiaKeresztelySzakaszokcpp14Accepted 100/100141ms15712 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;
}
SubtaskSumTestVerdictTimeMemory
base100/100
1Accepted0/03ms1832 KiB
2Accepted0/027ms4116 KiB
3Accepted2/23ms2012 KiB
4Accepted2/24ms2576 KiB
5Accepted2/26ms2840 KiB
6Accepted3/313ms3560 KiB
7Accepted3/37ms3436 KiB
8Accepted3/320ms4548 KiB
9Accepted3/321ms4760 KiB
10Accepted4/421ms4736 KiB
11Accepted4/427ms5000 KiB
12Accepted4/439ms6632 KiB
13Accepted7/756ms8420 KiB
14Accepted7/770ms9500 KiB
15Accepted7/783ms10756 KiB
16Accepted7/7140ms15664 KiB
17Accepted7/745ms7236 KiB
18Accepted7/783ms10628 KiB
19Accepted7/793ms11424 KiB
20Accepted7/7141ms15460 KiB
21Accepted7/7140ms15712 KiB
22Accepted7/771ms14024 KiB