Submission #747526

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
747526	2023-05-24T09:17:16 Z	vjudge1	Kralj (COCI16_kralj)	C++17	0 / 140	365 ms	111584 KB

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],opnwi[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];
  }

  int mx=0;
  for (int i=1;i<n;i++) {
    if (mx<sfx[i]) {
      mx=sfx[i]; str=i;
    }
  }
}

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;
      opnwi[nwi[i]]=i;
    }

    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<<nwi[i]<<' ';cout<<endl;
    //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[opnwi[i]]);
      if (dl==*st.end()) dl=*st.begin();
      st.erase(dl);
      //cout<<p[opnwi[i]]<<' '<<dl<<endl;
      if (dl>p[opnwi[i]]) ans++;
    }
    cout<<ans;
}

Compilation message

kralj.cpp: In function 'void start()':
kralj.cpp:20:7: warning: unused variable 'prfx' [-Wunused-variable]
   20 |   int prfx[n],sfx[n];
      |       ^~~~

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	257 ms	89516 KB	Execution killed with signal 11
2	Runtime error	254 ms	87528 KB	Execution killed with signal 11
3	Runtime error	320 ms	108772 KB	Execution killed with signal 11
4	Runtime error	316 ms	111584 KB	Execution killed with signal 11
5	Runtime error	365 ms	65684 KB	Execution killed with signal 11
6	Runtime error	269 ms	65192 KB	Execution killed with signal 11
7	Runtime error	324 ms	68208 KB	Execution killed with signal 11
8	Runtime error	263 ms	61268 KB	Execution killed with signal 11
9	Runtime error	340 ms	72092 KB	Execution killed with signal 11
10	Runtime error	310 ms	72144 KB	Execution killed with signal 11