Submission #989057

#	Time	Username	Problem	Language	Result	Execution time	Memory
989057		AdamGS	Comparing Plants (IOI20_plants)	C++17	19 / 100	362 ms	119632 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#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=2e5+7, INF=1e9+7, LG=20;
set<int>A, B;
pair<int,int>tr[4*LIM];
int lazy[4*LIM], T[LIM], gdzie[LIM], nxt[LIM][LG], prv[LIM][LG], n, k, N=1;
int tr2[4*LIM];
ll sumnxt[LIM][LG], sumprv[LIM][LG];
void spl(int v) {
  tr[2*v].st+=lazy[v];
  tr[2*v+1].st+=lazy[v];
  lazy[2*v]+=lazy[v];
  lazy[2*v+1]+=lazy[v];
  lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
  if(r<a || b<l) return;
  if(a<=l && r<=b) {
    tr[v].st+=x;
    lazy[v]+=x;
    return;
  }
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, x);
  upd(2*v+1, mid+1, r, a, b, x);
  tr[v]=min(tr[2*v], tr[2*v+1]);
}
pair<int,int>cnt(int v, int l, int r, int a, int b) {
  if(r<a || b<l) return {INF, INF};
  if(a<=l && r<=b) return tr[v];
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  return min(cnt(2*v, l, mid, a, b), cnt(2*v+1, mid+1, r, a, b));
}
int dyst(int a, int b) {
  if(a<b) return b-a;
  return n-a+b;
}
pair<int,int>licz(int x) {
  auto it=A.lower_bound(x);
  int a=-1, b=-1;
  if(it==A.end()) {
    auto it2=A.begin();
    b=*it2;
  } else b=*it;
  if(it==A.begin()) {
    auto it2=A.end(); --it2;
    a=*it2;
  } else {
    --it;
    a=*it;
  }
  return {a, b};
}
void dodaj(int x) {
  if(A.size()==0) {
    A.insert(x);
    B.insert(x);
    return;
  }
  pair<int,int>p=licz(x);
  int a=p.st, b=p.nd;
  if(dyst(x, b)<k && B.find(b)!=B.end()) B.erase(b);
  if(dyst(a, x)>=k) B.insert(x);
  A.insert(x);
}
void usun(int x) {
  A.erase(x);
  if(B.find(x)!=B.end()) B.erase(x);
  if(A.size()==1) B.insert(*A.begin());
  if(A.size()<2) return;
  pair<int,int>p=licz(x);
  int a=p.st, b=p.nd;
  if(dyst(a, b)>=k) B.insert(b);
}
void upd2(int v, int x) {
  v+=N;
  tr2[v]=x;
  v/=2;
  while(v) {
    tr2[v]=min(tr2[2*v], tr2[2*v+1]);
    v/=2;
  }
}
int cnt2(int l, int r) {
  l+=N; r+=N;
  int ans=min(tr2[l], tr2[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=min(ans, tr2[l+1]);
    if(r%2==1) ans=min(ans, tr2[r-1]);
    l/=2; r/=2;
  }
  return ans;
}
void init(int _k, vector<int>r) {
  n=r.size(); k=_k;
  while(N<n) N*=2;
  rep(i, n) tr[N+i]={r[i], i};
  for(int i=n; i<N; ++i) tr[N+i]={INF, INF};
  for(int i=N-1; i; --i) tr[i]=min(tr[2*i], tr[2*i+1]);
  rep(i, n) {
    while(tr[1].st==0) {
      dodaj(tr[1].nd);
      upd(1, 0, N-1, tr[1].nd, tr[1].nd, INF);
    }
    int x=*B.begin();
    usun(x);
    upd(1, 0, N-1, x-k+1, x, -1);
    if(x-k+1<0) upd(1, 0, N-1, n+x-k+1, n-1, -1);
    T[x]=n-i-1;
    gdzie[n-i-1]=x;
  }
  rep(i, 2*N) tr2[i]=INF;
  for(int i=n-1; i>=0; --i) {
    int p=gdzie[i];
    int a=cnt2(p, min(p+k-1, n-1));
    if(p+k-1>n-1) a=min(a, cnt2(0, p+k-1-n));
    int b=cnt2(max(0, p-k+1), p);
    if(p-k+1<0) b=min(b, cnt2(n+p-k+1, n-1));
    if(a==INF) a=i;
    if(b==INF) b=i;
    nxt[i][0]=a;
    prv[i][0]=b;
    sumnxt[i][0]=dyst(p, gdzie[a]);
    sumprv[i][0]=dyst(gdzie[b], p);
    upd2(p, i);
  }
  for(int j=1; j<LG; ++j) rep(i, n) {
    nxt[i][j]=nxt[nxt[i][j-1]][j-1];
    prv[i][j]=prv[prv[i][j-1]][j-1];
    sumnxt[i][j]=sumnxt[i][j-1]+sumnxt[nxt[i][j-1]][j-1];
    sumprv[i][j]=sumprv[i][j-1]+sumprv[prv[i][j-1]][j-1];
  }
}
bool mniejszy(int x, int y) {
  if(x>y) return false;
  if(nxt[x][LG-1]>=y) {
    int p=x;
    ll a=dyst(gdzie[x], gdzie[y]), b=0;
    for(int i=LG-1; i>=0; --i) if(nxt[p][i]<=y) {
      b+=sumnxt[p][i];
      p=nxt[p][i];
    }
    if(b>=a) return true;
  }
  if(prv[x][LG-1]>=y) {
    int p=x;
    ll a=dyst(gdzie[y], gdzie[x]), b=0;
    for(int i=LG-1; i>=0; --i) if(prv[p][i]<=y) {
      b+=sumprv[p][i];
      p=prv[p][i];
    }
    if(b>=a) return true;
  }
  return false;
}
int compare_plants(int x, int y) {
  if(mniejszy(T[x], T[y])) return -1;
  if(mniejszy(T[y], T[x])) return 1;
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25