oj.uz

Submission #1109512

# Submission time Handle Problem Language Result Execution time Memory
1109512 2024-11-07T00:57:07 Z tinnhiemnn trapezoid (balkan11_trapezoid) C++14
40 / 100
 65 ms 7156 KB 
#include <bits/stdc++.h>
using namespace std;
#define file "test"
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
const int N=1e5+2, INF=1e6;
int n,a[N],b[N],c[N],d[N],bit[INF+2],res,f[N];
vector<int> v;

struct hihi
{
    int x,y,id;
    bool operator < (const hihi &o) const
    {
        if (x!=o.x) return x < o.x; else return id > o.id;
    }
};
vector<hihi> event;

void update(int x, int val)
{
    for (; x<=INF; x+=x&-x) bit[x]=max(bit[x], val);
}
int get(int x)
{
    int res=0; for (; x>0; x-=x&-x) res=max(res, bit[x]);
    return res;
}
int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        v.pb(c[i]); v.pb(d[i]);
    }

    sort(all(v)); v.resize(unique(all(v)) - v.begin());

    for (int i=1;i<=n;i++)
    {
        c[i] = lower_bound(all(v), c[i]) - v.begin()+1;
        d[i] = lower_bound(all(v), d[i]) - v.begin()+1;

        event.pb({a[i], c[i], i});
        event.pb({b[i], d[i], -i});
    }

    sort(all(event));

    for (hihi e : event)
    {
        int y=e.y;
        if (e.id > 0)
        {
            f[e.id] = get(y-1) + 1;
            res=max(res, f[e.id]);
        }
        else update(y, f[-e.id]);
    }
    cout<<res<<' '<<1;

}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Partially correct 1 ms 336 KB Partially correct
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 2 ms 592 KB Partially correct
5 Partially correct 2 ms 760 KB Partially correct
6 Partially correct 4 ms 592 KB Partially correct
7 Partially correct 4 ms 848 KB Partially correct
8 Partially correct 4 ms 848 KB Partially correct
9 Partially correct 8 ms 1164 KB Partially correct
10 Partially correct 16 ms 2000 KB Partially correct
11 Partially correct 17 ms 1900 KB Partially correct
12 Partially correct 35 ms 3648 KB Partially correct
13 Partially correct 41 ms 4160 KB Partially correct
14 Partially correct 47 ms 6272 KB Partially correct
15 Partially correct 55 ms 6680 KB Partially correct
16 Partially correct 57 ms 6592 KB Partially correct
17 Partially correct 60 ms 6600 KB Partially correct
18 Partially correct 62 ms 6848 KB Partially correct
19 Partially correct 62 ms 6940 KB Partially correct
20 Partially correct 65 ms 7156 KB Partially correct