Submission #493579

#	Time	Username	Problem	Language	Result	Execution time	Memory
493579		600Mihnea	Financial Report (JOI21_financial)	C++17	48 / 100	4048 ms	26540 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 300000 + 7;
int n;
int d;
int a[N];
int dp[N];
int order[N];

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

struct Node {
  int pref = 0;
  int suf = 0;
  int l;
  int r;
  int last = 0;
};

Node operator + (Node a, Node b) {
  assert(a.r + 1 == b.l);
  int pref = a.pref + b.pref * (a.pref == a.r - a.l + 1);
  int suf = b.suf + a.suf * (b.suf == b.r - b.l + 1);
  int l = a.l;
  int r = a.r;
  int last = 0;
  if (a.last) {
    last = a.last;
  } else {
    if (a.suf + b.pref >= d) {
      last = (a.r - a.suf + 1) + d - 1;
    } else {
      last = b.last;
    }
  }

  return {suf, pref, l, r, last};
}

Node tree[4 * N];

void build(int v, int tl, int tr) {
  tree[v].l = tl;
  tree[v].r = tr;
  if (tl < tr) {
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
  }
}

void setup(int v, int tl, int tr, int i) {
  if (tr < i || i < tl) {
    return;
  }
  if (tl == tr) {
    tree[v].suf = tree[v].pref = 1;
  } else {
    int tm = (tl + tr) / 2;
    setup(2 * v, tl, tm, i);
    setup(2 * v, tm + 1, tr, i);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
  }
}

bool deja[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];
    order[i] = i;
  }

  sort(order + 1, order + n + 1, cmp);
  for (int it = 1; it <= n; it++) {
    int i = order[it];
    deja[i] = 1;
    dp[i] = 0;
    int bigger = 0;
    int last;
    for (int j = i + 1; j <= n; j++) {
      dp[i] = max(dp[i], dp[j]);
      last = i;
      if (deja[j]) {
        bigger++;
      } else {
        bigger = 0;
      }
      if (bigger == d) {
        break;
      }
    }
    dp[i]++;
  }
  int sol = 0;
  for (int i = 1; i <= n; i++) {
    sol = max(sol, dp[i]);
  }
  cout << sol << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:95:9: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   95 |     int last;
      |         ^~~~

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