12972022-03-30 22:30:48k_balintSzakaszokcpp14Elfogadva 100/10081ms28388 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ÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/03ms1836 KiB
2Elfogadva0/014ms3852 KiB
3Elfogadva2/21ms2312 KiB
4Elfogadva2/23ms2564 KiB
5Elfogadva2/23ms2736 KiB
6Elfogadva3/38ms3088 KiB
7Elfogadva3/34ms3128 KiB
8Elfogadva3/312ms4228 KiB
9Elfogadva3/312ms4524 KiB
10Elfogadva4/412ms4884 KiB
11Elfogadva4/414ms5664 KiB
12Elfogadva4/423ms7048 KiB
13Elfogadva7/728ms8888 KiB
14Elfogadva7/737ms10424 KiB
15Elfogadva7/748ms13424 KiB
16Elfogadva7/779ms19544 KiB
17Elfogadva7/724ms13124 KiB
18Elfogadva7/743ms17376 KiB
19Elfogadva7/754ms19108 KiB
20Elfogadva7/781ms25040 KiB
21Elfogadva7/779ms26988 KiB
22Elfogadva7/739ms28388 KiB