Submission #225813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
225813	2020-04-21T18:18:25 Z	osaaateiasavtnl	Kralj (COCI16_kralj)	C++14	14 / 140	2000 ms	84192 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];
set <int> add[N];
bool used[N];

bool comp(int i, int j) {
    return p1[i] > p1[j];
}   
 
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]].insert(p2[i]);
    }
    int ans = 0;         
    set <int> can;
    for (int i = 1; i <= n; ++i)
        if (add[i].size())
            can.insert(i);

    vector <int> per;
    for (int i = 1; i <= n; ++i)
        per.app(i);
    sort(all(per), comp);

    while (can.size()) {
        bool did = 0;
        for (int i : per) {
            if (used[i])
                continue;

            int j;

            {
            auto t = can.upper_bound(i);
            if (t == can.begin()) {
                j = *can.rbegin();
            }   
            else {
                j = *prev(t);
            }
            }   

            auto t = add[j].upper_bound(p1[i]);
            if (t != add[j].end()) {
                ++ans;
                add[j].erase(t);
                did = 1;
                used[i] = 1;
                if (add[j].empty())
                    can.erase(j);
            }   
        }   
        if (!did) {
            for (int i : per) {
                if (used[i])
                    continue;

                int j;

                {
                auto t = can.upper_bound(i);
                if (t == can.begin()) {
                    j = *can.rbegin();
                }   
                else {
                    j = *prev(t);
                }
                }   

                used[i] = 1;
                add[j].erase(add[j].begin());
                if (add[j].empty())
                    can.erase(j);
                break;
            }   
        }   
    }

    cout << ans << endl;
}

Subtask #1

14.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1274 ms	65128 KB	Output is correct
2	Execution timed out	2033 ms	63764 KB	Time limit exceeded
3	Execution timed out	2089 ms	72672 KB	Time limit exceeded
4	Execution timed out	2094 ms	73220 KB	Time limit exceeded
5	Execution timed out	2089 ms	72508 KB	Time limit exceeded
6	Execution timed out	2095 ms	73196 KB	Time limit exceeded
7	Execution timed out	2089 ms	82144 KB	Time limit exceeded
8	Execution timed out	2089 ms	78188 KB	Time limit exceeded
9	Execution timed out	2093 ms	84192 KB	Time limit exceeded
10	Execution timed out	2084 ms	77792 KB	Time limit exceeded