1407 2022. 09. 02 02:09:02 Zoli9 Szakaszok cpp17 Elfogadva 100/100 144ms 13848 KiB
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
int st[3000009];
vector<int> cop;

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

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

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<pii, pii > > obj;
    cop.resize(n+2*m);
    int x, y, z;
    for (int i=0; i<n; i++){
        cin >> x >> y >> z;
        obj.push_back({{x, -1*1e5}, {z, 0}});
        obj.push_back({{y, 1e5}, {z, 0}});
        cop[i] = z;
    }
    for (int i=0; i<m; i++){
        cin >> x >> y >> z;
        obj.push_back({{x, i+1},{y, z}});
        cop[n+2*i] = y;
        cop[n+2*i+1] = z;
    }
    sort(cop.begin(), cop.end());
    cop.erase(unique(cop.begin(), cop.end()), cop.end());
    sort(obj.begin(), obj.end());
    pii maxi = {0, 0};
    for (auto i : obj){
        if (abs(i.fi.se) == 1e5){
            update(1, 1, cop.size()+1, comp(i.se.fi), i.fi.se / 1e5 * -1);
        }
        else{
            int cur = get(1, 1, cop.size()+1, comp(i.se.fi), comp(i.se.se));
            if (cur > maxi.fi){
                maxi = {cur, i.fi.se};
            }
        }
    }
    cout << maxi.second;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 1832 KiB
2 Elfogadva 0/0 27ms 3900 KiB
3 Elfogadva 2/2 2ms 2480 KiB
4 Elfogadva 2/2 4ms 2664 KiB
5 Elfogadva 2/2 4ms 2932 KiB
6 Elfogadva 3/3 13ms 3668 KiB
7 Elfogadva 3/3 7ms 3572 KiB
8 Elfogadva 3/3 20ms 4452 KiB
9 Elfogadva 3/3 21ms 4708 KiB
10 Elfogadva 4/4 21ms 4648 KiB
11 Elfogadva 4/4 27ms 4824 KiB
12 Elfogadva 4/4 41ms 6232 KiB
13 Elfogadva 7/7 54ms 7264 KiB
14 Elfogadva 7/7 68ms 7992 KiB
15 Elfogadva 7/7 82ms 8564 KiB
16 Elfogadva 7/7 144ms 13096 KiB
17 Elfogadva 7/7 45ms 6576 KiB
18 Elfogadva 7/7 82ms 8688 KiB
19 Elfogadva 7/7 97ms 10436 KiB
20 Elfogadva 7/7 143ms 13680 KiB
21 Elfogadva 7/7 143ms 13680 KiB
22 Elfogadva 7/7 74ms 13848 KiB