oj.uz

Submission #201174

# Submission time Handle Problem Language Result Execution time Memory
201174 2020-02-09T15:08:46 Z SamAnd Kralj (COCI16_kralj) C++17
140 / 140
 931 ms 54992 KB 
#include <bits/stdc++.h>
using  namespace std;
const int N = 500005;

int n;
int u[N];
int d[N];
int e[N];
vector<int> v[N];

int q[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &u[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &d[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &e[i]);
    for (int i = 1; i <= n; ++i)
    {
        q[u[i]]++;
        v[u[i]].push_back(e[i]);
    }
    for (int i = 1; i <= n; ++i)
    {
        q[i] = q[i] + q[i - 1];
    }
    for (int i = 1; i <= n; ++i)
    {
        q[i] = q[i] - i;
    }
    int minu = q[1];
    int mini = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (q[i] < minu)
        {
            minu = q[i];
            mini = i;
        }
    }
    ++mini;
    if (mini == n + 1)
        mini = 1;
    int ans = 0;
    multiset<int> s;
    for (int i = mini; i <= n; ++i)
    {
        for (int j = 0; j < v[i].size(); ++j)
        {
            int x = v[i][j];
            s.insert(x);
        }
        multiset<int>::iterator it = s.lower_bound(d[i]);
        if (it == s.end())
        {
            s.erase(s.begin());
        }
        else
        {
            ++ans;
            s.erase(it);
        }
    }
    for (int i = 1; i < mini; ++i)
    {
        for (int j = 0; j < v[i].size(); ++j)
        {
            int x = v[i][j];
            s.insert(x);
        }
        multiset<int>::iterator it = s.lower_bound(d[i]);
        if (it == s.end())
        {
            s.erase(s.begin());
        }
        else
        {
            ++ans;
            s.erase(it);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

kralj.cpp: In function 'int main()':
kralj.cpp:52:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
kralj.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
kralj.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
kralj.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &u[i]);
         ~~~~~^~~~~~~~~~~~~
kralj.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
kralj.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &e[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 931 ms 47412 KB Output is correct
2 Correct 606 ms 46152 KB Output is correct
3 Correct 753 ms 54500 KB Output is correct
4 Correct 750 ms 54992 KB Output is correct
5 Correct 456 ms 34144 KB Output is correct
6 Correct 398 ms 34168 KB Output is correct
7 Correct 550 ms 38016 KB Output is correct
8 Correct 436 ms 36216 KB Output is correct
9 Correct 542 ms 39416 KB Output is correct
10 Correct 456 ms 35960 KB Output is correct