Submission #853268

#	Time	Username	Problem	Language	Result	Execution time	Memory
853268		sofijavelkovska	사다리꼴 (balkan11_trapezoid)	C++14	76 / 100	158 ms	6084 KiB

trapezoid

#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 (stderr)

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 / 100