Submission #366586

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
366586	2021-02-14T16:39:33 Z	Atill83	Kralj (COCI16_kralj)	C++14	140 / 140	668 ms	64040 KB

kralj

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 1e6+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
int a[MAXN], p[MAXN], v[MAXN];
int suf[MAXN];
int yer[MAXN];
vector<int> kc[MAXN];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n;

    vector<int> ot;

    for(int i = 1; i <= n; i++){
        cin>>a[i];
        yer[a[i]]++;
        yer[a[i] + n]++;
    }
    
    for(int i = 1; i <= n; i++){
        cin>>p[i];
        p[n + i] = p[i];
    }

    for(int i = 1; i <= n; i++){
        cin>>v[i];
        kc[a[i]].push_back(v[i]);
        kc[a[i] + n].push_back(v[i]);
    }

    for(int i = n; i >= 1; i--)
        suf[i] = suf[i + 1] + yer[i];
    
    int left = n + 1;

    for(int j = n; j >= 1; j--){
        if(suf[j] - suf[left] >= left - j + 1){
            left = j;
        }
    }

    set<int> st;
    int ans = 0;
    for(int j = left + n - 1; j >= left; j--){
        sort(kc[j].begin(), kc[j].end());
        st.insert(p[j]);

        for(int l: kc[j]){
            assert(!st.empty());
            auto u = st.upper_bound(l);
            if(u == st.begin()){
                st.erase(prev(st.end()));
            }else{
                st.erase(prev(u));
                ans++;
            }
        }
    }
    cout<<ans<<endl;


    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	517 ms	55640 KB	Output is correct
2	Correct	518 ms	54752 KB	Output is correct
3	Correct	668 ms	62732 KB	Output is correct
4	Correct	661 ms	64040 KB	Output is correct
5	Correct	459 ms	45292 KB	Output is correct
6	Correct	508 ms	46188 KB	Output is correct
7	Correct	607 ms	51948 KB	Output is correct
8	Correct	488 ms	51136 KB	Output is correct
9	Correct	639 ms	53400 KB	Output is correct
10	Correct	537 ms	47980 KB	Output is correct