oj.uz

Submission #931193

# Submission time Handle Problem Language Result Execution time Memory
931193 2024-02-21T11:09:42 Z 12345678 trapezoid (balkan11_trapezoid) C++17
2 / 100
 90 ms 31736 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) 
    {
        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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4696 KB Partially correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Incorrect 2 ms 4696 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 9 ms 5980 KB Output isn't correct
10 Incorrect 17 ms 7504 KB Output isn't correct
11 Incorrect 20 ms 8228 KB Output isn't correct
12 Incorrect 44 ms 11844 KB Output isn't correct
13 Incorrect 52 ms 13124 KB Output isn't correct
14 Runtime error 70 ms 27744 KB Execution killed with signal 11
15 Incorrect 72 ms 15524 KB Output isn't correct
16 Incorrect 77 ms 16184 KB Output isn't correct
17 Runtime error 87 ms 31736 KB Execution killed with signal 11
18 Incorrect 77 ms 17616 KB Output isn't correct
19 Incorrect 83 ms 18292 KB Output isn't correct
20 Incorrect 90 ms 19004 KB Output isn't correct