Submission #1440584


Source Code Expand

#include<bits/stdc++.h>

using namespace std;

int N, M, a[100009], b[100009], c[100009], d[100009], e[100009], v[100009], ans[100009], aib[100009];
vector < int > g[100009], h[100009];

void refresh (int &x)
{
    x = lower_bound (c + 1, c + N + 3, x) - c;
}

void U (int pos, int val)
{
    while (pos <= N + 1)
        aib[pos] += val, pos += pos - (pos & (pos - 1));
}

int Q (int pos)
{
    int ans = 0;
    while (pos)
        ans += aib[pos], pos &= pos - 1;
    return ans;
}

multiset < pair < int, int > > used, S;
void useSegm (int i, int j)
{
    U (i, +1);
    U (j + 1, -1);
    used.insert ({i, j});
}

void adSegm (int i, int j)
{
    //printf ("[%d, %d]\n", i, j);
    g[j].push_back (i);
    h[i].push_back (j);
}

int getAns (int i, int j)
{
    int currAns = -1;
    if (ans[i - 1] != -1) currAns = max (currAns, N + 1 - ans[i - 1]);
    if (ans[j - 1] != -1) currAns = max (currAns, N - ans[j - 1]);
    return currAns;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
for (int i=1; i<=N; i++)
    scanf ("%d %d", &a[i], &b[i]);
for (int i=1; i<=N + 1; i++)
    scanf ("%d", &c[i]), v[i] = -1;
sort (c + 1, c + N + 2), c[N + 2] = 1e9 + 10;
scanf ("%d", &M);
for (int i=1; i<=M; i++)
    scanf ("%d %d", &d[i], &e[i]), refresh (d[i]), refresh (e[i]);
for (int i=1; i<=N; i++)
{
    refresh (a[i]), refresh (b[i]), v[a[i]] ++;
    if (b[i] < a[i])
        adSegm (b[i], a[i] - 1);
}
for (int i=1; i<=N + 1; i++)
    v[i] += v[i - 1];
//for (int i=1; i<=N + 1; i++)
  //  printf ("%d%c", v[i], " \n"[i == N + 1]);
for (int i=N + 1; i>=1; i--)
{
    for (auto lft : g[i])
        S.insert ({lft, i});
    int curr = v[i] + Q(i);
    while (curr < -1 && !S.empty ())
    {
        auto it = S.begin ();
        useSegm (it->first, it->second), S.erase (it), ans[0] ++;
        curr ++;
    }
    if (curr < -1)
    {
        for (int i=1; i<=M; i++)
            printf ("-1\n");
        return 0;
    }
}
S.clear ();
for (int i=1; i<=N + 1; i++)
{
    for (auto rgt : h[i])
        if (used.find ({i, rgt}) != used.end ()) used.erase (used.find ({i, rgt}));
        else S.insert ({rgt, i});
    ans[i] = ans[i - 1];
    int curr = v[i] + Q(i);
    while (curr < 0 && !S.empty ())
    {
        auto it = S.end (); it --;
        useSegm (it->second, it->first), S.erase (it), ans[i] ++;
        curr ++;
    }
    if (curr < 0)
    {
        for (int j=i; j<=N + 1; j++)
            ans[j] = -1;
        break;
    }
}
for (int i=1; i<=M; i++)
    printf ("%d\n", getAns (d[i], e[i]));
return 0;
}

Submission Info

Submission Time
Task F - Two Faced Cards
User geniucos
Language C++14 (GCC 5.4.1)
Score 2000
Code Size 2686 Byte
Status AC
Exec Time 199 ms
Memory 19584 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:55:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
                 ^
./Main.cpp:57:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &a[i], &b[i]);
                                  ^
./Main.cpp:59:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &c[i]), v[i] = -1;
                                   ^
./Main.cpp:61:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &M);
                 ^
./Main.cpp:63:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &d[i], &e[i]), refr...

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 2000 / 2000
Status
AC × 3
AC × 61
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt
Case Name Status Exec Time Memory
sample_01.txt AC 3 ms 6400 KB
sample_02.txt AC 3 ms 6400 KB
sample_03.txt AC 3 ms 6400 KB
subtask_1_01.txt AC 66 ms 10112 KB
subtask_1_02.txt AC 96 ms 13312 KB
subtask_1_03.txt AC 36 ms 8320 KB
subtask_1_04.txt AC 100 ms 14592 KB
subtask_1_05.txt AC 49 ms 9216 KB
subtask_1_06.txt AC 109 ms 15104 KB
subtask_1_07.txt AC 87 ms 13312 KB
subtask_1_08.txt AC 134 ms 16896 KB
subtask_1_09.txt AC 112 ms 15104 KB
subtask_1_10.txt AC 61 ms 13056 KB
subtask_1_11.txt AC 47 ms 10112 KB
subtask_1_12.txt AC 67 ms 11520 KB
subtask_1_13.txt AC 81 ms 12032 KB
subtask_1_14.txt AC 46 ms 11392 KB
subtask_1_15.txt AC 61 ms 11648 KB
subtask_1_16.txt AC 37 ms 8576 KB
subtask_1_17.txt AC 163 ms 18176 KB
subtask_1_18.txt AC 38 ms 11008 KB
subtask_1_19.txt AC 86 ms 11264 KB
subtask_1_20.txt AC 145 ms 16768 KB
subtask_1_21.txt AC 154 ms 13312 KB
subtask_1_22.txt AC 198 ms 19584 KB
subtask_1_23.txt AC 154 ms 13312 KB
subtask_1_24.txt AC 199 ms 19584 KB
subtask_1_25.txt AC 170 ms 18432 KB
subtask_1_26.txt AC 157 ms 19200 KB
subtask_1_27.txt AC 122 ms 14336 KB
subtask_1_28.txt AC 182 ms 18304 KB
subtask_1_29.txt AC 169 ms 18432 KB
subtask_1_30.txt AC 165 ms 19200 KB
subtask_1_31.txt AC 124 ms 14336 KB
subtask_1_32.txt AC 181 ms 18304 KB
subtask_1_33.txt AC 168 ms 18432 KB
subtask_1_34.txt AC 153 ms 19200 KB
subtask_1_35.txt AC 122 ms 14336 KB
subtask_1_36.txt AC 181 ms 18304 KB
subtask_1_37.txt AC 170 ms 18432 KB
subtask_1_38.txt AC 160 ms 19200 KB
subtask_1_39.txt AC 124 ms 14336 KB
subtask_1_40.txt AC 198 ms 18304 KB
subtask_1_41.txt AC 140 ms 11904 KB
subtask_1_42.txt AC 107 ms 9728 KB
subtask_1_43.txt AC 149 ms 14720 KB
subtask_1_44.txt AC 112 ms 10240 KB
subtask_1_45.txt AC 96 ms 8960 KB
subtask_1_46.txt AC 130 ms 11520 KB
subtask_1_47.txt AC 96 ms 8704 KB
subtask_1_48.txt AC 132 ms 13824 KB
subtask_1_49.txt AC 103 ms 9472 KB
subtask_1_50.txt AC 88 ms 8576 KB
subtask_1_51.txt AC 3 ms 6400 KB
subtask_1_52.txt AC 3 ms 6400 KB
subtask_1_53.txt AC 3 ms 6400 KB
subtask_1_54.txt AC 3 ms 6400 KB
subtask_1_55.txt AC 3 ms 6400 KB