oj.uz

Submission #747475

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

vector<int> v[500001];
vector<int> vec;
multiset<int> s;
int ans;
int ind, sz;

void solve() {
    for(int i = ind; i < sz; i++) {
        assert(!s.empty());
        auto it = s.upper_bound(vec[i]);
        if(it != s.end()) {
            ans++;
            s.erase(it);
        }
        else
            s.erase(s.begin());
    }
    ind = sz;
}
const int N = 1e6 + 5;
    int a[N], b[N], c[N], be[N], en[N];

signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
    int n;
    cin >> 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; i++) {
        x += (be[i] > 0);
        if(be[i] && x == 1)
            st = i;
        x -= en[i];
    }
    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++) {
        if(be[st] || i == n)
            solve();
        for(int j : v[st])
            s.insert(j);
        vec.push_back(b[st]);
        st++;
        sz++;
        st %= n;
    }
    cout << ans;

    return 0;
}

Subtask #1
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 42000 KB Output is correct
2 Correct 663 ms 41376 KB Output is correct
3 Correct 855 ms 47584 KB Output is correct
4 Correct 796 ms 48180 KB Output is correct
5 Runtime error 181 ms 50976 KB Execution killed with signal 6
6 Runtime error 236 ms 51396 KB Execution killed with signal 6
7 Runtime error 248 ms 57216 KB Execution killed with signal 6
8 Runtime error 222 ms 55708 KB Execution killed with signal 6
9 Runtime error 282 ms 58940 KB Execution killed with signal 6
10 Runtime error 252 ms 53732 KB Execution killed with signal 6