Submission #225790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
225790	2020-04-21T16:22:03 Z	osaaateiasavtnl	Kralj (COCI16_kralj)	C++14	56 / 140	589 ms	60224 KB

kralj

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 5e5 + 7;
int a[N], p1[N], p2[N];
vector <int> add[N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }   
    for (int i = 1; i <= n; ++i)
        cin >> p1[i];
    for (int i = 1; i <= n; ++i) {
        cin >> p2[i];
        add[a[i]].app(p2[i]);
    }                

    int mx = 1;
    for (int i = 1; i <= n; ++i) {
        if (add[i].size() > add[mx].size())
            mx = i;
    }   

    int ans = 0;
    for (int s = mx; s <= mx; ++s) {
        set <int> cur;
        priority_queue <ii> q;
        bool ban = 0;
        int nn = 0;
        for (int sh = 0; sh < n; ++sh) {
            int i = s + sh;
            if (i > n)
                i -= n;
            for (int x : add[i]) {
                q.push(mp(sh, x));
            }   
            if (cur.empty() && q.size()) {
                int r = q.top().f;
                while (q.size() && q.top().f == r) {
                    cur.insert(q.top().s);
                    q.pop();
                }   
            }   
            if (cur.empty()) {
                ban = 1;
                break;
            }   
            auto t = cur.upper_bound(p1[i]);
            if (t == cur.end()) {
                cur.erase(cur.begin());
            }   
            else {
                ++nn;
                cur.erase(t);
            }   
        }
        if (!ban) {
            ans = max(ans, nn);
        }   
    }   
    cout << ans << endl;
}

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	582 ms	51276 KB	Output is correct
2	Correct	448 ms	50640 KB	Output is correct
3	Correct	466 ms	59072 KB	Output is correct
4	Correct	589 ms	60224 KB	Output is correct
5	Incorrect	231 ms	30180 KB	Output isn't correct
6	Incorrect	267 ms	30328 KB	Output isn't correct
7	Incorrect	297 ms	32456 KB	Output isn't correct
8	Incorrect	259 ms	30840 KB	Output isn't correct
9	Incorrect	349 ms	33528 KB	Output isn't correct
10	Incorrect	289 ms	31992 KB	Output isn't correct