Submission #494059

#	Time	Username	Problem	Language	Result	Execution time	Memory
494059		MEGalodon	trapezoid (balkan11_trapezoid)	C++14	44 / 100	142 ms	14856 KiB

trapezoid

#include <bits/stdc++.h>
#define MAXN 100000
#define ii pair<int, int>
#define iii pair<int, ii>
#define f first
#define s second
using namespace std;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
vector<int> coOrd;
vector<iii> ABs;
class SegmentTree{
private:
    int n;
    vector<ii> st;

    int left(int p){ return 2*p; }
    int right(int p){ return 2*p+1; }
    ii query(int p, int L, int R, int i, int j){
        if( i > R || j < L ) return {0, 0};
        if( L >= i && R <= j ) return st[p];
        int mid = (L+R)/2;
        ii p1 = query(left(p), L, mid, i, j);
        ii p2 = query(right(p), mid+1, R, i, j);
        if( p1.f > p2.f ) return p1;
        if( p1.f == p2.f ) return {p1.f, p1.s+p2.s};
        return p2;
    }
    void update(int p, int L, int R, int i, ii val){
        if( i > R || i < L ) return;
        if( L == i && R == i ){
            st[p] = val;
            return;
        }
        int mid = (L+R)/2;
        update(left(p), L, mid, i, val);
        update(right(p), mid+1, R, i, val);
        if( st[left(p)].f > st[right(p)].f ) st[p] = st[left(p)];
        else if( st[right(p)].f > st[left(p)].f ) st[p] = st[right(p)];
        else st[p] = {st[left(p)].f, st[left(p)].s+st[right(p)].s};
    }

public:
    SegmentTree(int A){
        n = A;
        st.assign(4*n, {0, 0});
    }
    void update(int i, ii val){ update(1,1,n,i,val); }
    ii query(int i){ return query(1,1,n,1,i); }
};
int output[MAXN], cnt[MAXN];
int main(){
  	ios_base::sync_with_stdio(false);
  	cin.tie(0); cout.tie(0);
    int trapezoids; cin>>trapezoids;
    for( int i{1} ; i <= trapezoids ; ++i ){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        coOrd.push_back(c[i]); coOrd.push_back(d[i]);
        ABs.push_back(iii(a[i], ii(i, 1))); ABs.push_back(iii(b[i], ii(i, -1)));
    }
    sort(coOrd.begin(), coOrd.end());
    coOrd.erase(unique(coOrd.begin(), coOrd.end()), coOrd.end());
    sort(ABs.begin(), ABs.end());
    SegmentTree st((int)coOrd.size()+10);
    for( int i{1} ; i <= trapezoids ; ++i ){
        c[i] = lower_bound(coOrd.begin(), coOrd.end(), c[i])-coOrd.begin();
        d[i] = lower_bound(coOrd.begin(), coOrd.end(), d[i])-coOrd.begin();
    }
    int o = 0;
    for( auto x : ABs ){
        int t = x.s.f;
        int type = x.s.s;
        ii q = st.query(c[t]);
        if( type == 1 ) output[t] = q.f+1, cnt[t] = max(1, q.s);
        else st.update(d[t], {output[t], cnt[t]});
        o = max(o, output[t]);
    }
    int cn = 0;
    for( int i{1} ; i <= trapezoids ; ++i ) if( output[i] == o ) cn += cnt[i];
    cout<<o<<" "<<cn<<'\n';
    return 0;
}

• Subtask 1: 44 / 100