oj.uz

Submission #747521

# Submission time Handle Problem Language Result Execution time Memory
747521 2023-05-24T08:57:37 Z vjudge1 Kralj (COCI16_kralj) C++17
0 / 140
 345 ms 111532 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 269 ms 89592 KB Execution killed with signal 11
2 Runtime error 255 ms 87616 KB Execution killed with signal 11
3 Runtime error 337 ms 108764 KB Execution killed with signal 11
4 Runtime error 316 ms 111532 KB Execution killed with signal 11
5 Runtime error 340 ms 65724 KB Execution killed with signal 11
6 Runtime error 269 ms 65196 KB Execution killed with signal 11
7 Runtime error 317 ms 68308 KB Execution killed with signal 11
8 Runtime error 268 ms 61280 KB Execution killed with signal 11
9 Runtime error 345 ms 72140 KB Execution killed with signal 11
10 Runtime error 328 ms 72368 KB Execution killed with signal 11