oj.uz

Submission #1109511

# Submission time Handle Problem Language Result Execution time Memory
1109511 2024-11-07T00:53:24 Z tinnhiemnn trapezoid (balkan11_trapezoid) C++14
2 / 100
 50 ms 9328 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(a[i]); v.pb(b[i]); v.pb(c[i]); v.pb(d[i]);
    }

    for (int i=1;i<=n;i++)
    {
        a[i] = lower_bound(all(v), a[i]) - v.begin()+1;
        b[i] = lower_bound(all(v), b[i]) - v.begin()+1;
        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 x=e.x, 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;

}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:61:13: warning: unused variable 'x' [-Wunused-variable]
   61 |         int x=e.x, y=e.y;
      |             ^

Subtask #1
2.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Incorrect 1 ms 504 KB Output isn't correct
4 Incorrect 1 ms 592 KB Output isn't correct
5 Incorrect 2 ms 592 KB Output isn't correct
6 Incorrect 2 ms 848 KB Output isn't correct
7 Incorrect 4 ms 848 KB Output isn't correct
8 Incorrect 4 ms 848 KB Output isn't correct
9 Incorrect 5 ms 1232 KB Output isn't correct
10 Incorrect 12 ms 2240 KB Output isn't correct
11 Incorrect 13 ms 2392 KB Output isn't correct
12 Incorrect 24 ms 4296 KB Output isn't correct
13 Incorrect 30 ms 5076 KB Output isn't correct
14 Incorrect 37 ms 8648 KB Output isn't correct
15 Incorrect 38 ms 8648 KB Output isn't correct
16 Incorrect 47 ms 8904 KB Output isn't correct
17 Incorrect 50 ms 8896 KB Output isn't correct
18 Incorrect 45 ms 8820 KB Output isn't correct
19 Incorrect 42 ms 9328 KB Output isn't correct
20 Incorrect 47 ms 9152 KB Output isn't correct