Submission #989039

#	Time	Username	Problem	Language	Result	Execution time	Memory
989039		AdamGS	Comparing Plants (IOI20_plants)	C++17	0 / 100	5 ms	4808 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;
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 znajdz(int 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);
  upd(1, 0, N-1, x, x, INF);
  pair<int,int>a=cnt(1, 0, N-1, x+1, n-1);
  if(a.st==0) return a.nd;
  return cnt(1, 0, N-1, 0, x-1).nd;
}
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-1; i; --i) tr[i]=min(tr[2*i], tr[2*i+1]);
  int lst=-1, akt=-1;
  for(int i=n-1; i>=0; --i) if(r[i]==0) lst=i;
  for(int i=lst+1; i<n; ++i) if(r[i]==0) {
    if(i-lst>k-1) {
      akt=i;
      break;
    }
    lst=i;
  }
  rep(i, n) if(r[i]==0 && akt==-1) akt=i;
  T[akt]=n-1;
  for(int i=n-2; i>=0; --i) {
    akt=znajdz(akt);
    T[akt]=i;
  }
}
int compare_plants(int x, int y) {
	if(T[x]>T[y]) return 1;
  return -1;
}

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