답안 #366586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
366586 2021-02-14T16:39:33 Z Atill83 Kralj (COCI16_kralj) C++14
140 / 140
668 ms 64040 KB
#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
}
# 결과 실행 시간 메모리 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