제출 #747521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
747521		vjudge1	Kralj (COCI16_kralj)	C++17	0 / 140	345 ms	111532 KiB

kralj

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
int mod=1e9+7;
const int N=5e5+5;
template<class x>
using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;

int n,str=0;
int a[N],p[N],v[N],tmp[N],nwi[N];

void start() {
  for (int i=0;i<n;i++) {
    tmp[a[i]]++;
  }
  int prfx[n],sfx[n];
  for (int i=0;i<n;i++) {
    prfx[i]=tmp[i]-1;
    if (i>0) prfx[i]+=prfx[i-1];
  }
  for (int i=n-1;i>=0;i--) {
    sfx[i]=tmp[i]-1;
    if (i<n-1) sfx[i]+=sfx[i+1];
  }

  for (int i=1;i<n;i++) {
    if (prfx[i-1]+sfx[i]==0 && prfx[i-1]<0) {
      str=i; break;
    }
  }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(".in", "r", stdin); freopen(".out", "w", stdout);

    cin>>n;
    for (int i=0;i<n;i++) {cin>>a[i]; a[i]--;}
    for (int i=0;i<n;i++) cin>>p[i];
    for (int i=0;i<n;i++) cin>>v[i];
    start();

    for (int i=0;i<n;i++) {
      if (i<str) nwi[i]=(n-str)+i;
      else nwi[i]=i-str;
    }

    vector<pair<int,int> >nm;
    for (int i=0;i<n;i++) {
      nm.push_back({nwi[a[i]],v[i]});
    }
    sort(nm.begin(),nm.end());

    //for (int i=0;i<n;i++) cout<<nm[i].first<<' '<<nm[i].second<<endl; cout<<endl;

    set<int> st;
    int j=0,ans=0;
    for (int i=0;i<n;i++) {
      while (nm[j].first<=i) {
        st.insert(nm[j].second);
        j++;
      }
      int dl=*st.upper_bound(p[nwi[i]]);
      if (dl==*st.end()) dl=*st.begin();
      st.erase(dl);
      //cout<<p[nwi[i]]<<' '<<dl<<endl;
      if (dl>p[nwi[i]]) ans++;
    }
    cout<<ans;
}

• Subtask 1: 0 / 140