Submission #247483

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
247483	2020-07-11T13:04:23 Z	Vladikus004	Kralj (COCI16_kralj)	C++14	56 / 140	2000 ms	98764 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], e = 0;
        ind += sz[ind];
        do{
            ind %= n;
            e = 0;
            if (ind != a[i]){
                add_ed(ind);
                if (sz[ind]) e = 1;
                ind += sz[ind];
                sz[a[i]] += sz[ind];
                sz[ind] = 0;
            }
        }while (e);
        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;
}

Compilation message

kralj.cpp: In function 'int main()':
kralj.cpp:50:13: warning: unused variable 'go' [-Wunused-variable]
         int go = 0, ind = a[i], e = 0;
             ^~

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	712 ms	83940 KB	Output is correct
2	Correct	494 ms	82720 KB	Output is correct
3	Correct	644 ms	96868 KB	Output is correct
4	Correct	624 ms	98764 KB	Output is correct
5	Execution timed out	2081 ms	45304 KB	Time limit exceeded
6	Execution timed out	2079 ms	45036 KB	Time limit exceeded
7	Execution timed out	2082 ms	47484 KB	Time limit exceeded
8	Execution timed out	2090 ms	45560 KB	Time limit exceeded
9	Execution timed out	2088 ms	48736 KB	Time limit exceeded
10	Execution timed out	2084 ms	47224 KB	Time limit exceeded