Submission #904052

#	Time	Username	Problem	Language	Result	Execution time	Memory
904052		AdamGS	Giraffes (JOI22_giraffes)	C++17	100 / 100	3179 ms	3692 KiB

giraffes

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<pair<int,int>,pair<int,int>>kwad;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=8007, INF=1e9+7;
int P[LIM], tr[4*LIM], N=1, n;
pair<int,int>K[LIM];
void upd(int v, int x) {
  v+=N;
  while(v) {
    tr[v]=min(tr[v], x);
    v/=2;
  }
}
int cnt(int l, int r) {
  if(l>r) return INF;
  l+=N; r+=N;
  int ans=min(tr[l], tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=min(ans, tr[l+1]);
    if(r%2==1) ans=min(ans, tr[r-1]);
    l/=2; r/=2;
  }
  return ans;
}
pair<int,int>obr(pair<int,int>x) {
  return {n-1-x.nd, x.st};
}
kwad obrk(kwad x) {
  x={obr(x.st), obr(x.nd)};
  if(x.st.st>x.nd.st) swap(x.st.st, x.nd.st);
  if(x.st.nd>x.nd.nd) swap(x.st.nd, x.nd.nd);
  return x;
}
vector<kwad>solve(vector<kwad>T) {
  vector<kwad>V;
  rep(i, n) K[i]={i, P[i]};
  rep(xd, 4) {
    vector<int>mi(n, INF);
    vector<pair<int,int>>S;
    rep(i, n) S.pb({K[i].st-K[i].nd, -i-1});
    rep(i, T.size()) S.pb({T[i].st.st-T[i].st.nd, i+1});
    sort(all(S));
    reverse(all(S));
    rep(i, 2*N) tr[i]=INF;
    for(auto i : S) {
      int p=abs(i.nd)-1;
      if(i.nd<0) mi[p]=min(mi[p], cnt(K[p].nd+1, n-1)-K[p].st);
      else upd(T[p].st.nd, T[p].nd.st);
    }
    reverse(all(S));
    rep(i, 2*N) tr[i]=INF;
    for(auto i : S) {
      int p=abs(i.nd)-1;
      if(i.nd<0) mi[p]=min(mi[p], cnt(K[p].st+1, n-1)-K[p].nd);
      else upd(T[p].st.st, T[p].nd.nd);
    }
    rep(i, n) if(K[i].st+mi[i]<n && K[i].nd+mi[i]<n) V.pb({K[i], {K[i].st+mi[i], K[i].nd+mi[i]}});
    rep(i, n) K[i]=obr(K[i]);
    rep(i, T.size()) T[i]=obrk(T[i]);
    rep(i, V.size()) V[i]=obrk(V[i]);  
  }
  return V;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  while(N<n) N*=2;
  rep(i, n) {
    cin >> P[i];
    --P[i];
  }
  int ans=n;
  vector<kwad>T;
  rep(i, n) T.pb({{i, P[i]}, {i, P[i]}});
  while(T.size()) {
    --ans;
    T=solve(T);
  }
  cout << ans << '\n';
}

Compilation message (stderr)

giraffes.cpp: In function 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > solve(std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >)':
giraffes.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
giraffes.cpp:48:5: note: in expansion of macro 'rep'
   48 |     rep(i, T.size()) S.pb({T[i].st.st-T[i].st.nd, i+1});
      |     ^~~
giraffes.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
giraffes.cpp:66:5: note: in expansion of macro 'rep'
   66 |     rep(i, T.size()) T[i]=obrk(T[i]);
      |     ^~~
giraffes.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
giraffes.cpp:67:5: note: in expansion of macro 'rep'
   67 |     rep(i, V.size()) V[i]=obrk(V[i]);
      |     ^~~

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 41 / 41