oj.uz

Submission #747608

# Submission time Handle Problem Language Result Execution time Memory
747608 2023-05-24T11:39:56 Z vjudge1 Kralj (COCI16_kralj) C++17
56 / 140
 2000 ms 56872 KB 
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const ll mod = 1000000007;

vector<int> v[500001];
set<int> s;
int ans;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int a[n], b[n], c[n], be[n] = {}, en[n] = {};
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        be[a[i] - 1]++;
    }
    int x = 0;
    for(int i = 0; i < n; i++) {
        if(be[i]) {
            en[(i + be[i] - 1) % n]++;
            if(i + be[i] - 1 >= n)
                x++;
        }
    }
    int st = 0;
    for(int i = 0; i < n * 2; i++) {
        x += (be[i % n] > 0);
        if(i >= n && be[i % n] && x == 1)
            st = i % n;
        x -= en[i % n];
        x = max(x, 0);
    }
    for(int i = 0; i < n; i++)
        cin >> b[i];
    for(int i = 0; i < n; i++) {
        cin >> c[i];
        v[a[i] - 1].push_back(c[i]);
    }
    for(int i = 0; i < n; i++) {
        for(int j : v[st])
            s.insert(j);
        auto it = s.upper_bound(b[st]);
        if(it != s.end()) {
            ans++;
            s.erase(it);
        }
        else
            s.erase(s.begin());
        st++;
        st %= n;
    }
    cout << ans;

    return 0;
}

Subtask #1
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 48700 KB Output is correct
2 Correct 327 ms 47580 KB Output is correct
3 Correct 453 ms 56216 KB Output is correct
4 Correct 466 ms 56872 KB Output is correct
5 Execution timed out 2057 ms 35916 KB Time limit exceeded
6 Execution timed out 2051 ms 35620 KB Time limit exceeded
7 Execution timed out 2056 ms 39560 KB Time limit exceeded
8 Execution timed out 2052 ms 37580 KB Time limit exceeded
9 Execution timed out 2041 ms 41084 KB Time limit exceeded
10 Execution timed out 2053 ms 37692 KB Time limit exceeded