oj.uz

Submission #51728

# Submission time Handle Problem Language Result Execution time Memory
51728 2018-06-20T11:21:29 Z Costin Andrei Oncescu(#1294) Fortune Telling 2 (JOI14_fortune_telling2) C++11
0 / 100
 2 ms 376 KB 
#include<bits/stdc++.h>

using namespace std;

int N, K, aib[200009], id[200009], A[200009], B[200009], ans[200009], cnt[200009];
pair < int, int > h[200009];

bool cmp (int i, int j)
{
    return (min (A[i], B[i]) > min (A[j], B[j]));
}

void update (int pos, int val)
{
    while (pos <= K)
        aib[pos] = max (aib[pos], val),
        cnt[pos] ++,
        pos += pos - (pos & (pos - 1));
}

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

scanf ("%d %d", &N, &K);
for (int i=1; i<=N; i++)
    scanf ("%d %d", &A[i], &B[i]), id[i] = i;
sort (id + 1, id + N + 1, cmp);
for (int i=1; i<=K; i++)
    scanf ("%d", &h[i].first), h[i].second = i;
sort (h + 1, h + K + 1);
int j = K, lg = 0;
while ((2 << lg) <= K)
    lg ++;
long long sum = 0;
for (int ii=1; ii<=N; ii++)
{
    int i = id[ii];
    while (j > 0 && h[j].first >= min (A[i], B[i]))
        update (K - h[j].second + 1, h[j].first), j --;
    int pos = 0, followingSteps = 0;
    for (int k=lg; k>=0; k--)
        if (pos + (1 << k) <= K && aib[pos + (1 << k)] < max (A[i], B[i]))
            pos += 1 << k, followingSteps += cnt[pos];
    pos ++, pos = K - pos + 1;
    int val = 0;
    if (pos == 0)
        val = (K % 2 ? B[i] : A[i]);
    else
    {
        if (A[i] > B[i])
            swap (A[i], B[i]);
        val = (followingSteps % 2 ? B[i] : A[i]);
    }
    sum += val, ans[i] = val;
}
//for (int i=1; i<=N; i++)
  //  printf ("%d%c", ans[i], " \n"[i == N]);
printf ("%lld\n", sum);
return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &K);
 ~~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:28: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]), id[i] = i;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
fortune_telling2.cpp:31:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &h[i].first), h[i].second = i;
     ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -