oj.uz

Submission #853268

# Submission time Handle Problem Language Result Execution time Memory
853268 2023-09-23T19:29:38 Z sofijavelkovska trapezoid (balkan11_trapezoid) C++14
76 / 100
 158 ms 6084 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=(1<<17);
const int MOD=30013;

int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
pair<int, int> tree[2*MAXN-1]={{0, 0}};

bool compare(int x, int y)
{
    return a[x]<a[y];
}

pair<int, int> treemerge(pair<int, int> x, pair<int, int> y)
{
    if (x.first==y.first)
        return {x.first, (x.second+y.second)%MOD};

    return max(x, y);
}

void update(int x, int l, int r, int i, pair<int, int> value)
{
    if (l>i || r<=i)
        return;
    tree[x]=treemerge(tree[x], value);
    if (r-l==1)
        return;
    update(2*x+1, l, (l+r)/2, i, value);
    update(2*x+2, (l+r)/2, r, i, value);

    return;
}

pair<int, int> find(int x, int l, int r, int lt, int rt)
{
    if (l>=rt || r<=lt)
        return {0, 0};
    if (l>=lt && r<=rt)
        return tree[x];

    return treemerge(find(2*x+1, l, (l+r)/2, lt, rt), find(2*x+2, (l+r)/2, r, lt, rt));
}

int main()
{
    int n, maxcardinality, totalways=0, i, j;
    priority_queue<pair<int, int> > pq;
    cin >> n;
    int asorted[n], dpmax[n], dpcount[n];
    pair<int, int> dsorted[n];
    for (i=0; i<n; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    for (i=0; i<n; i++)
        asorted[i]=i;
    sort(asorted, asorted+n, compare);
    for (i=0; i<n; i++)
        dsorted[i]={d[i], i};
    sort(dsorted, dsorted+n);
    for (i=0; i<n; i++)
    {
        dpmax[i]=1;
        dpcount[i]=1;
        while (!pq.empty() && -pq.top().first<a[asorted[i]])
        {
            int j=pq.top().second;
            int maxlower=lower_bound(dsorted, dsorted+n, make_pair(d[asorted[j]], -1))-dsorted;
            update(0, 0, MAXN, maxlower, {dpmax[j], dpcount[j]});
            pq.pop();
        }
        int maxlower=lower_bound(dsorted, dsorted+n, make_pair(c[asorted[i]], asorted[i]))-dsorted;
        //cout << asorted[i]+1 << " " << maxlower << '\n';
        if (maxlower!=0)
        {
            auto result=find(0, 0, MAXN, 0, maxlower);
            //cout << "result " << result.first+1 << " " << result.second << '\n';
            dpmax[i]=result.first+1;
            dpcount[i]=result.second;
        }
        pq.push({-b[asorted[i]], i});
    }
    maxcardinality=*max_element(dpmax, dpmax+n);
    for (i=0; i<n; i++)
        if (dpmax[i]==maxcardinality)
            totalways=(totalways+dpcount[i])%MOD;
    cout << maxcardinality << " " << totalways;

    return 0;
}



/*#include <bits/stdc++.h>
using namespace std;

const int MAXN=100000;
const int MOD=30013;

int a[MAXN], b[MAXN], c[MAXN], d[MAXN];

bool compare(int x, int y)
{
    return b[x]<b[y];
}

bool intersect(int x, int y)
{
    if (b[x]>a[y])
        return true;
    if (d[x]>c[y])
        return true;

    return false;
}

int main()
{
    int n, maxcardinality, totalways=0, i, j;
    cin >> n;
    int sorted[n], dpmax[n], dpcount[n];
    for (i=0; i<n; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    for (i=0; i<n; i++)
        sorted[i]=i;
    sort(sorted, sorted+n, compare);
    for (i=0; i<n; i++)
    {
        dpmax[i]=1;
        dpcount[i]=1;
        for (j=0; j<i; j++)
        {
            if (!intersect(sorted[j], sorted[i]))
            {
                if (dpmax[j]+1>dpmax[i])
                {
                    dpmax[i]=dpmax[j]+1;
                    dpcount[i]=dpcount[j];
                }
                else if (dpmax[j]+1==dpmax[i])
                    dpcount[i]=(dpcount[i]+dpcount[j])%30013;
            }
        }
    }
    maxcardinality=*max_element(dpmax, dpmax+n);
    for (i=0; i<n; i++)
        if (dpmax[i]==maxcardinality)
            totalways=(totalways+dpcount[i])%MOD;
    cout << maxcardinality << " " << totalways;

    return 0;
}*/

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:48:44: warning: unused variable 'j' [-Wunused-variable]
   48 |     int n, maxcardinality, totalways=0, i, j;
      |                                            ^

Subtask #1
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Partially correct 1 ms 2392 KB Partially correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Partially correct 4 ms 2396 KB Partially correct
7 Correct 6 ms 2648 KB Output is correct
8 Partially correct 7 ms 2648 KB Partially correct
9 Correct 14 ms 2704 KB Output is correct
10 Correct 27 ms 3160 KB Output is correct
11 Correct 36 ms 3164 KB Output is correct
12 Correct 88 ms 4140 KB Output is correct
13 Partially correct 93 ms 4556 KB Partially correct
14 Correct 108 ms 4812 KB Output is correct
15 Partially correct 119 ms 5204 KB Partially correct
16 Partially correct 127 ms 5556 KB Partially correct
17 Correct 141 ms 5612 KB Output is correct
18 Correct 127 ms 5756 KB Output is correct
19 Partially correct 141 ms 5824 KB Partially correct
20 Partially correct 158 ms 6084 KB Partially correct