oj.uz

Submission #1109516

# Submission time Handle Problem Language Result Execution time Memory
1109516 2024-11-07T01:35:33 Z tinnhiemnn trapezoid (balkan11_trapezoid) C++14
100 / 100
 82 ms 12488 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=2e5+2, mod=30013;
int n,a[N],b[N],c[N],d[N],bit[INF+2],bit2[INF+2],res,f[N],ans,dp[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,tr[N];

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;
}
void update2(int x, int val)
{
    for (; x<=INF; x+=x&-x) bit2[x]=(bit2[x]+val)%mod;
}
int get2(int x)
{
    int res=0; for (; x>0; x-=x&-x) res=(res+bit2[x])%mod;
    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]);
            tr[f[e.id]-1].pb({e.x, e.y, e.id}); if (f[e.id] == 1) dp[e.id] = 1;
        }
        else {
            update(y, f[-e.id]); tr[f[-e.id]].pb({e.x, e.y, e.id});
        }
    }

    for (int i=1;i<res;i++)
    {
        sort(all(tr[i])); //cout<<i<<": ";
        for (hihi e : tr[i])
        {
            int y=e.y; //cout<<e.id<<' ';
            if (e.id > 0)
            {
                dp[e.id] = get2(y-1);
            }
            else {
                update2(y, dp[-e.id]);
            }
        }
        for (hihi e : tr[i]) if (e.id < 0) update2(e.y, -dp[-e.id]);
    }
    //for (int i=1;i<=n;i++) cout<<dp[i]<<' ';

    for (int i=1;i<=n;i++) if (f[i] == res) ans=(ans + dp[i])%mod;
    cout<<res<<' '<<ans;

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 2 ms 4780 KB Output is correct
4 Correct 2 ms 4688 KB Output is correct
5 Correct 3 ms 4688 KB Output is correct
6 Correct 4 ms 4944 KB Output is correct
7 Correct 4 ms 4944 KB Output is correct
8 Correct 5 ms 5184 KB Output is correct
9 Correct 11 ms 5516 KB Output is correct
10 Correct 18 ms 6256 KB Output is correct
11 Correct 21 ms 6732 KB Output is correct
12 Correct 42 ms 8520 KB Output is correct
13 Correct 50 ms 9280 KB Output is correct
14 Correct 62 ms 10624 KB Output is correct
15 Correct 62 ms 10836 KB Output is correct
16 Correct 69 ms 11196 KB Output is correct
17 Correct 71 ms 11264 KB Output is correct
18 Correct 78 ms 12100 KB Output is correct
19 Correct 75 ms 12220 KB Output is correct
20 Correct 82 ms 12488 KB Output is correct