Submission #195594

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
195594	2020-01-16T15:28:31 Z	stefdasca	Kralj (COCI16_kralj)	C++14	56 / 140	484 ms	75476 KB

kralj

#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;

int solve(int st)
{
    int ss = 0;
    int dif = 0;
    vector<int> va, vb;
    for(int i = st; i <= st + n - 1; ++i)
    {
        dif--;
        va.pb(skill[i - (i > n) * n]);
        for(int j = 0; j < enemy[i].size(); ++j)
            vb.pb(skill2[enemy[i][j] - (enemy[i][j] > n) * n]), ++dif;
        if(dif == 0)
        {
            sort(va.begin(), va.end());
            sort(vb.begin(), vb.end());
            int pa = 0;
            for(int j = 0; j < va.size(); ++j)
            {
                while(pa < vb.size() && vb[pa] < va[j])
                    ++pa;
                if(pa < vb.size())
                    ++ss, ++pa;
                else
                    break;
            }
            va.clear();
            vb.clear();
            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], ++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];
    deque<int> mn;
    for(int i = 1; i < 2 * n; ++i)
    {
        sp[i] = sp[i-1] + frq[i - n * (i > n)] - 1;
        if(i > n && !mn.empty() && mn[0] == i - n)
            mn.pop_front();
        while(!mn.empty() && sp[i] < sp[mn.back()])
            mn.pop_back();
        mn.pb(i);
        if(i >= n && sp[mn[0]] >= sp[i - n])
            ans = max(ans, solve(i - n + 1));
    }
    cout << ans;
    return 0;
}

Compilation message

kralj.cpp: In function 'int solve(int)':
kralj.cpp:36:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < enemy[i].size(); ++j)
                        ~~^~~~~~~~~~~~~~~~~
kralj.cpp:43:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < va.size(); ++j)
                            ~~^~~~~~~~~~~
kralj.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(pa < vb.size() && vb[pa] < va[j])
                       ~~~^~~~~~~~~~~
kralj.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(pa < vb.size())
                    ~~~^~~~~~~~~~~

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	253 ms	33360 KB	Output is correct
2	Correct	236 ms	32504 KB	Output is correct
3	Correct	296 ms	36612 KB	Output is correct
4	Correct	301 ms	36580 KB	Output is correct
5	Runtime error	316 ms	65024 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	376 ms	66544 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	443 ms	74064 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	375 ms	69504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	484 ms	75476 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	480 ms	72364 KB	Execution killed with signal 11 (could be triggered by violating memory limits)