Submission #247473

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
247473	2020-07-11T12:51:52 Z	Vladikus004	Kralj (COCI16_kralj)	C++14	0 / 140	2000 ms	67832 KB

kralj

#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 500000 + 5;
int n, a[N], p[N], v[N], us[N], cnt, sz[N], was_ed[N];
vector <int> gr[N], add[N];

void add_ed(int x){
    if (was_ed[x]) return;
    gr[(x - 1 + n) % n].push_back(x);
    was_ed[x] = 1;
}

int ans = 0;
multiset <int> ms;
void dfs(int x){
    us[x] = 1;
    if (gr[x].size()) dfs(gr[x][0]);
    ms.insert(p[x]);
    for (auto u: add[x]){
        auto it = ms.lower_bound(u);
        if (it == ms.begin()){
            ms.erase(ms.lower_bound(*ms.rbegin()));
        }else{
            --it;
            ms.erase(it);
            ans++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n; i++) cin >> v[i];
    for (int i = 0; i < n; i++){
        a[i]--;
        int go = 0, ind = a[i];
        do{
            go += sz[ind];
            if (ind != a[i]){
                add_ed(ind);
                sz[a[i]] += sz[ind];
                sz[ind] = 0;
            }
            ind++;
            ind %= n;
        }while (go--);
        add[a[i]].push_back(v[i]);
        sz[a[i]]++;
    }
    for (int i = 0; i < n; i++){
        if (was_ed[i] || us[i]) continue;
        dfs(i);
    }
    cout << ans;
}

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2094 ms	38264 KB	Time limit exceeded
2	Execution timed out	2099 ms	37624 KB	Time limit exceeded
3	Execution timed out	2099 ms	40568 KB	Time limit exceeded
4	Execution timed out	2089 ms	40668 KB	Time limit exceeded
5	Execution timed out	2096 ms	67156 KB	Time limit exceeded
6	Execution timed out	2081 ms	66372 KB	Time limit exceeded
7	Execution timed out	2090 ms	65144 KB	Time limit exceeded
8	Execution timed out	2090 ms	61560 KB	Time limit exceeded
9	Execution timed out	2085 ms	67832 KB	Time limit exceeded
10	Execution timed out	2089 ms	64248 KB	Time limit exceeded