Submission #931193

#	Time	Username	Problem	Language	Result	Execution time	Memory
931193		12345678	trapezoid (balkan11_trapezoid)	C++17	2 / 100	90 ms	31736 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];

struct fenwick 
{
    value d[nx];
    void add(int i, value x) 
    {
        i++;
        while (i<nx) d[i]=(d[i]+x), i+=(i&-i);
    }
    value query(int i)
    {
        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(d[B[p].second], dp[p]), p++;
        dp[i]=f.query(c[A[i].second]-1);
        dp[i].mx++;
        if (dp[i].f==0) dp[i].f=1;
    }
    cout<<dp[n-1].mx<<' '<<dp[n-1].f;
}

• Subtask 1: 2 / 100