oj.uz

Submission #113905

# Submission time Handle Problem Language Result Execution time Memory
113905 2019-05-29T07:26:08 Z Kastanda trapezoid (balkan11_trapezoid) C++11
10 / 100
 151 ms 26836 KB 
#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() + 1);
    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

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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 10108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 6 ms 4992 KB Output is correct
3 Runtime error 13 ms 10240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 14 ms 10240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 15 ms 10240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 17 ms 10624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 16 ms 10496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 13 ms 5660 KB Output is correct
9 Runtime error 25 ms 11520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 33 ms 13304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 43 ms 14036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 80 ms 18436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 88 ms 19976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 104 ms 21876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 122 ms 22984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 136 ms 24092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 138 ms 24696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 122 ms 25020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 131 ms 25720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 151 ms 26836 KB Execution killed with signal 11 (could be triggered by violating memory limits)