oj.uz

Submission #195634

# Submission time Handle Problem Language Result Execution time Memory
195634 2020-01-16T16:30:20 Z stefdasca Kralj (COCI16_kralj) C++14
140 / 140
 881 ms 55016 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, rival[500002];

int frq[500002], sp[1000002];

vector<int> enemy[500002];
int skill[500002], skill2[500002];

int ans = 0;
set<int> vb;

int solve(int st)
{
    int ss = 0;
    vb.clear();
    for(int i = st; i <= st + n - 1; ++i)
    {
        int truepos = i;
        if(truepos > n)
            truepos -= n;
        for(int j = 0; j < enemy[truepos].size(); ++j)
            vb.insert(skill2[enemy[truepos][j]]);
        if(skill[truepos] > *vb.rbegin())
            vb.erase(vb.begin());
        else
            ++ss, vb.erase(vb.lower_bound(skill[truepos]));
        if(ss + (st + n - 1) - i <= ans)
            return ss;
    }
    return ss;
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> rival[i];
    for(int i = 1; i <= n; ++i)
        ++frq[rival[i]], enemy[rival[i]].pb(i);
    for(int i = 1; i <= n; ++i)
        cin >> skill[i];
    for(int i = 1; i <= n; ++i)
        cin >> skill2[i];
    int mn = 1;
    for(int i = 1; i <= n; ++i)
    {
        sp[i] = sp[i-1] + frq[i] - 1;
        if(i >= 2 && sp[i] < sp[mn])
            mn = i;
    }
    mn++;
    if(mn > n)
        mn -= n;
    ans = solve(mn);
    cout << ans;
    return 0;
}

Compilation message

kralj.cpp: In function 'int solve(int)':
kralj.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < enemy[truepos].size(); ++j)
                        ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 47344 KB Output is correct
2 Correct 553 ms 46140 KB Output is correct
3 Correct 688 ms 54504 KB Output is correct
4 Correct 699 ms 55016 KB Output is correct
5 Correct 457 ms 31684 KB Output is correct
6 Correct 358 ms 35936 KB Output is correct
7 Correct 513 ms 35028 KB Output is correct
8 Correct 435 ms 37940 KB Output is correct
9 Correct 633 ms 35956 KB Output is correct
10 Correct 450 ms 33020 KB Output is correct