제출 #493574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493574		600Mihnea	Financial Report (JOI21_financial)	C++17	0 / 100	4059 ms	7820 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 300000 + 7;
int n, d, a[N], ord[N], l[N], r[N], t[N];

bool cmp(int i, int j) {
  if (a[i] != a[j]) {
    return a[i] > a[j];
  } else {
    return i < j;
  }
}

int getroot(int a) {
  if (t[a] == a) {
    return a;
  } else {
    return t[a] = getroot(t[a]);
  }
}

set<int> p;

void unite(int a, int b) {
  a = getroot(a);
  b = getroot(b);
  if (a == b) {
    return;
  }
  assert(a < b);
  assert(r[a] == a);
  assert(r[b] == b);
  assert(l[a] <= r[a] && r[a] < l[b] && l[b] <= r[b]);

  for (int j = l[a]; j <= r[a]; j++) {
    if (r[a] - j < d && r[b] - j >= d) {
      p.insert(j);
    }
  }

  t[a] = b;
  l[b] = l[a];

}

int last[N], tree[4 * N];

void upd(int v, int tl, int tr, int i, int x) {
  if (tr < i || i < tl) {
    return;
  }
  if (tl == tr) {
    tree[v] = x;
    return;
  }
  int tm = (tl + tr) / 2;
  upd(2 * v, tl, tm, i, x);
  upd(2 * v + 1, tm + 1, tr, i, x);
  tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}


int get(int v, int tl, int tr, int l, int r) {
  if (tr < l || r < tl) {
    return 0;
  }
  if (l <= tl && tr <= r) {
    return tree[v];
  }
  int tm = (tl + tr) / 2;
  return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
}

int rldp[N];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

 /// freopen ("TonyStark", "r", stdin);

  cin >> n >> d;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    ord[i] = i;
  }
  sort(ord + 1, ord + n + 1, cmp);

  for (int it = 1; it <= n; it++) {
    int i = ord[it];
    {
      auto iter = p.lower_bound(i);
      if (iter == p.end()) {
        last[i] = n;
      } else {
        last[i] = min(*iter - 1 + d, n);
      }
      assert(i <= last[i]);
    }
    int dp = get(1, 1, n, i, last[i]) + 1;
    cout << i << ", " << last[i] << " : " << dp << "\n";
    upd(1, 1, n, i, dp);
    l[i] = r[i] = t[i] = i;
    if (l[i - 1]) {
      unite(i - 1, i);
    }
    if (l[i + 1]) {
      unite(i, i + 1);
    }
  }
  cout << get(1, 1, n, 1, n) << "\n";

}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35