oj.uz

Submission #494059

# Submission time Handle Problem Language Result Execution time Memory
494059 2021-12-14T06:39:19 Z MEGalodon trapezoid (balkan11_trapezoid) C++14
44 / 100
 142 ms 14856 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 2 ms 464 KB Partially correct
5 Partially correct 3 ms 644 KB Partially correct
6 Partially correct 3 ms 848 KB Partially correct
7 Partially correct 4 ms 984 KB Partially correct
8 Partially correct 7 ms 1196 KB Partially correct
9 Partially correct 17 ms 1840 KB Partially correct
10 Partially correct 24 ms 3416 KB Partially correct
11 Partially correct 31 ms 4068 KB Partially correct
12 Partially correct 70 ms 7832 KB Partially correct
13 Partially correct 92 ms 9176 KB Partially correct
14 Partially correct 102 ms 10676 KB Partially correct
15 Partially correct 111 ms 11340 KB Partially correct
16 Partially correct 116 ms 12064 KB Partially correct
17 Partially correct 126 ms 12900 KB Partially correct
18 Partially correct 123 ms 13448 KB Partially correct
19 Partially correct 136 ms 14236 KB Partially correct
20 Runtime error 142 ms 14856 KB Execution killed with signal 11