Submission #989045

#	Time	Username	Problem	Language	Result	Execution time	Memory
989045		AdamGS	Comparing Plants (IOI20_plants)	C++17	44 / 100	238 ms	23028 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;
set<int>A, B;
pair<int,int>tr[4*LIM];
int lazy[4*LIM], T[LIM], n, k, N=1;
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 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;
  }
}
int compare_plants(int x, int y) {
  if(T[x]>T[y]) return 1;
  return -1;
}

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