답안 #747526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
747526 2023-05-24T09:17:16 Z vjudge1 Kralj (COCI16_kralj) C++17
0 / 140
365 ms 111584 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],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];
      |       ^~~~
# 결과 실행 시간 메모리 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