Submission #201174

#	Time	Username	Problem	Language	Result	Execution time	Memory
201174		SamAnd	Kralj (COCI16_kralj)	C++17	140 / 140	931 ms	54992 KiB

kralj

#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 (stderr)

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 / 140