Submission #931196

#	Time	Username	Problem	Language	Result	Execution time	Memory
931196		12345678	trapezoid (balkan11_trapezoid)	C++17	100 / 100	133 ms	16440 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, mod=30013;

int n, a[nx], b[nx], c[nx], d[nx], t, p;
vector<pair<int, int>> A, B;
map<int, int> mp;

struct value
{
    int mx, f;
    value(): mx(0), f(0) {}
    value(int mx, int f): mx(mx), f(f) {}
    friend value operator+(const value &lhs, const value &rhs) {
        if (lhs.mx>rhs.mx) return lhs;
        if (lhs.mx<rhs.mx) return rhs;
        return value(lhs.mx, (lhs.f+rhs.f)%mod);
    }
} dp[nx], ans;

struct fenwick 
{
    value d[nx];
    void add(int i, value x) 
    {
        while (i<nx) d[i]=(d[i]+x), i+=(i&-i);
    }
    value query(int i)
    {
        value res=value(0, 0);
        while (i>0) res=(res+d[i]), i-=(i&-i);
        return res; 
    }
} f;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=0; i<n; i++) cin>>a[i]>>b[i]>>c[i]>>d[i], A.push_back({a[i], i}), B.push_back({b[i], i}), mp[c[i]]=0, mp[d[i]]=0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    for (auto &[x, y]:mp) y=++t;
    for (int i=0; i<n; i++)
    {
        while (B[p].first<A[i].first) f.add(mp[d[B[p].second]], dp[B[p].second]), p++;
        dp[A[i].second]=f.query(mp[c[A[i].second]]-1);
        dp[A[i].second].mx++;
        if (dp[A[i].second].f==0) dp[A[i].second].f=1;
        ans=ans+dp[A[i].second];
    }
    cout<<ans.mx<<' '<<ans.f;
}

/*
3
1 2 1 2
3 4 3 4
5 6 5 6
*/

• Subtask 1: 100 / 100