Submission #113906

#	Time	Username	Problem	Language	Result	Execution time	Memory
113906		Kastanda	trapezoid (balkan11_trapezoid)	C++11	100 / 100	140 ms	12124 KiB

trapezoid

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 100005, Mod = 30013;
int n, A[N], B[N], C[N], D[N], P[N], dp[N], cn[N];
set < pair < int , int > > S, TB;
vector < int > vec[N], F[N];
inline bool CMP(int i, int j)
{
    return (A[i] < A[j]);
}
inline void Add(vector < int > &G, int i, int vl)
{
    for (i ++; i <= (int)G.size(); i += i & -i)
    {
        G[i] += vl;
        if (G[i] >= Mod)
            G[i] -= Mod;
    }
}
inline int Get(vector < int > &G, int i)
{
    int rt = 0;
    for (i ++; i; i -= i & -i)
    {
        rt += G[i];
        if (rt >= Mod)
            rt -= Mod;
    }
    return (rt);
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]), P[i] = i;
    sort(P, P + n, CMP);
    for (int j = 0; j < n; j++)
    {
        int i = P[j];
        dp[i] = 1;

        while (TB.size() && TB.begin()->first < A[i])
        {
            int id = TB.begin()->second;
            TB.erase(TB.begin());

            auto it = S.lower_bound(make_pair(D[id], 0));
            while (it != S.end())
            {
                if (it->second > dp[id])
                    break;
                it = S.erase(it);
            }
            if (it != S.begin())
            {
                it --;
                if (it->second >= dp[id])
                    continue;
            }
            S.insert(make_pair(D[id], dp[id]));
        }

        auto it = S.lower_bound(make_pair(C[i], 0));
        if (it != S.begin())
            it --, dp[i] = it->second + 1;

        TB.insert(make_pair(B[i], i));
        vec[dp[i]].push_back(D[i]);
    }
    for (int i = 1; i <= n; i++)
        sort(vec[i].begin(), vec[i].end()), F[i].resize((int)vec[i].size() + 5);
    TB.clear();
    for (int j = 0; j < n; j++)
    {
        int i = P[j];

        while (TB.size() && TB.begin()->first < A[i])
        {
            int id = TB.begin()->second;
            TB.erase(TB.begin());

            int lb = lower_bound(vec[dp[id]].begin(), vec[dp[id]].end(), D[id]) - vec[dp[id]].begin();
            Add(F[dp[id]], lb, cn[id]);
        }

        if (dp[i] > 1)
        {
            int lb = upper_bound(vec[dp[i] - 1].begin(), vec[dp[i] - 1].end(), C[i]) - vec[dp[i] - 1].begin() - 1;
            cn[i] = Get(F[dp[i] - 1], lb);
        }
        else
            cn[i] = 1;

        TB.insert(make_pair(B[i], i));
    }
    int Mx = 0, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (Mx < dp[i])
            Mx = dp[i], cnt = 0;
        if (Mx == dp[i])
        {
            cnt += cn[i];
            if (cnt >= Mod)
                cnt -= Mod;
        }
    }
    return !printf("%d %d\n", Mx, cnt);
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
trapezoid.cpp:36:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]), P[i] = i;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100