1297 2022. 03. 30 22:30:48 k_balint Szakaszok cpp14 Elfogadva 100/100 81ms 28388 KiB
#include <bits/stdc++.h>
using namespace std;
typedef pair<pair<int,int>,pair<int,int>> pii;
const int c=150002;

int fen[c];

void update(int pos, int val){
    for(;pos<c;pos+=pos&-pos){
        fen[pos]+=val;
    }
}

int query(int pos){
    int res=0;
    for(;pos>0;pos-=pos&-pos){
        res+=fen[pos];
    }
    return res;
}

vector<int> comp;

inline int f(int k){
    return (lower_bound(comp.begin(),comp.end(),k)-comp.begin())+1;
}

int n,m;
vector<pii> v;

inline int read(){
    int res=0; char ch=getchar();
    while(ch<'0' || '9'<ch) ch=getchar();
    while('0'<=ch && ch<='9'){
        res=(res<<3) + (res<<1) + ch-'0';
        ch=getchar();
    }
    return res;
}

int maxi;
int ans;

int main(){
    m=read(); n=read();
    
    for(int i=1;i<=m;i++){
        int x1,x2,y; x1=read(); x2=read(); y=read();
        v.emplace_back(make_pair(make_pair(x1,0),make_pair(y,0)));
        v.emplace_back(make_pair(make_pair(x2,c),make_pair(y,0)));
        comp.emplace_back(y);
    }

    for(int i=1;i<=n;i++){
        int x,y1,y2; x=read(); y1=read(); y2=read();
        v.emplace_back(make_pair(make_pair(x,i),make_pair(y1,y2)));
        comp.emplace_back(y1);
        comp.emplace_back(y2);
    }

    sort(v.begin(),v.end());
    sort(comp.begin(),comp.end());
    comp.resize(unique(comp.begin(),comp.end())-comp.begin());

    maxi=0; ans=0;

    for(int i=0;i<n+2*m;i++){
        if(v[i].first.second==0){
            update(f(v[i].second.first),1);
        }
        else if(v[i].first.second==c){
            update(f(v[i].second.first),-1);
        }
        else{  
            int id=v[i].first.second;
            int y1=f(v[i].second.first);
            int y2=f(v[i].second.second);
            int cur=query(y2)-query(y1-1);
            if(cur>maxi || (cur==maxi && id < ans)){
                ans=id;
                maxi=cur;
            }
        }
    }

    cout << ans << endl;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 1836 KiB
2 Elfogadva 0/0 14ms 3852 KiB
3 Elfogadva 2/2 1ms 2312 KiB
4 Elfogadva 2/2 3ms 2564 KiB
5 Elfogadva 2/2 3ms 2736 KiB
6 Elfogadva 3/3 8ms 3088 KiB
7 Elfogadva 3/3 4ms 3128 KiB
8 Elfogadva 3/3 12ms 4228 KiB
9 Elfogadva 3/3 12ms 4524 KiB
10 Elfogadva 4/4 12ms 4884 KiB
11 Elfogadva 4/4 14ms 5664 KiB
12 Elfogadva 4/4 23ms 7048 KiB
13 Elfogadva 7/7 28ms 8888 KiB
14 Elfogadva 7/7 37ms 10424 KiB
15 Elfogadva 7/7 48ms 13424 KiB
16 Elfogadva 7/7 79ms 19544 KiB
17 Elfogadva 7/7 24ms 13124 KiB
18 Elfogadva 7/7 43ms 17376 KiB
19 Elfogadva 7/7 54ms 19108 KiB
20 Elfogadva 7/7 81ms 25040 KiB
21 Elfogadva 7/7 79ms 26988 KiB
22 Elfogadva 7/7 39ms 28388 KiB