oj.uz

Submission #931195

# Submission time Handle Problem Language Result Execution time Memory
931195 2024-02-21T11:10:33 Z 12345678 trapezoid (balkan11_trapezoid) C++17
2 / 100
 117 ms 16288 KB 
#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) 
    {
        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[p]), p++;
        dp[i]=f.query(mp[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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB Partially correct
2 Incorrect 2 ms 4696 KB Output isn't correct
3 Incorrect 1 ms 4696 KB Output isn't correct
4 Incorrect 2 ms 4700 KB Output isn't correct
5 Incorrect 3 ms 4956 KB Output isn't correct
6 Incorrect 4 ms 4956 KB Output isn't correct
7 Incorrect 4 ms 5212 KB Output isn't correct
8 Incorrect 6 ms 5212 KB Output isn't correct
9 Incorrect 10 ms 5872 KB Output isn't correct
10 Incorrect 18 ms 6896 KB Output isn't correct
11 Incorrect 24 ms 7508 KB Output isn't correct
12 Incorrect 58 ms 10564 KB Output isn't correct
13 Incorrect 64 ms 11836 KB Output isn't correct
14 Incorrect 77 ms 12964 KB Output isn't correct
15 Incorrect 92 ms 13372 KB Output isn't correct
16 Incorrect 101 ms 14148 KB Output isn't correct
17 Incorrect 102 ms 14648 KB Output isn't correct
18 Incorrect 86 ms 15164 KB Output isn't correct
19 Incorrect 100 ms 15672 KB Output isn't correct
20 Incorrect 117 ms 16288 KB Output isn't correct