oj.uz

Submission #989050

# Submission time Handle Problem Language Result Execution time Memory
989050 2024-05-27T11:04:58 Z AdamGS Comparing Plants (IOI20_plants) C++17
5 / 100
 250 ms 57668 KB 
#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];
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;
    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];
  }
}
bool mniejszy(int x, int y) {
  if(x>y) return false;
  if(nxt[x][LG-1]>=y) {
    int p=x;
    for(int i=LG-1; i>=0; --i) if(nxt[p][i]<=y) p=nxt[p][i];
    if(p==y) return true;
  }
  if(prv[x][LG-1]>=y) {
    int p=x;
    for(int i=LG-1; i>=0; --i) if(prv[p][i]<=y) p=prv[p][i];
    if(p==y) 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 36 ms 10360 KB Output is correct
7 Correct 72 ms 14672 KB Output is correct
8 Correct 203 ms 54864 KB Output is correct
9 Correct 197 ms 52984 KB Output is correct
10 Correct 197 ms 52860 KB Output is correct
11 Correct 194 ms 53328 KB Output is correct
12 Correct 222 ms 53108 KB Output is correct
13 Correct 250 ms 57668 KB Output is correct
14 Correct 170 ms 48252 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Incorrect 1 ms 6492 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Incorrect 1 ms 6492 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 1 ms 8540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Incorrect 1 ms 6492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 36 ms 10360 KB Output is correct
7 Correct 72 ms 14672 KB Output is correct
8 Correct 203 ms 54864 KB Output is correct
9 Correct 197 ms 52984 KB Output is correct
10 Correct 197 ms 52860 KB Output is correct
11 Correct 194 ms 53328 KB Output is correct
12 Correct 222 ms 53108 KB Output is correct
13 Correct 250 ms 57668 KB Output is correct
14 Correct 170 ms 48252 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 6488 KB Output is correct
19 Incorrect 1 ms 6492 KB Output isn't correct
20 Halted 0 ms 0 KB -