Submission #493584

#	Time	Username	Problem	Language	Result	Execution time	Memory
493584		600Mihnea	Financial Report (JOI21_financial)	C++17	100 / 100	739 ms	39400 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 nothing = 0;
  int pref = 0;
  int suf = 0;
  int l;
  int r;
  int last = 0;
};

Node none;

Node operator + (Node a, Node b) {
  if (a.nothing) return b;
  if (b.nothing) return a;
  if (a.r + 1 != b.l) {
    cout << ": " << a.l << " " << a.r << " <-> " << b.l << " " << b.r << "\n";
    exit(0);
  }
  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 = b.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;
    }
  }
  a.nothing = 0;
  a.pref = pref;
  a.suf = suf;
  a.l = l;
  a.r = r;
  a.last = last;

  return a;
}

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 + 1, tm + 1, tr, i);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
  }
}

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

bool deja[N];

int t[4 * N];

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

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

signed main() { none.nothing = 1;
  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;
  }
  build(1, 1, n);

  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 = get(1, 1, n, i + 1, n).last;
    setup(1, 1, n, i);
    if (!last) {
      last = n;
    }
    upd(1, 1, n, i, gett(1, 1, n, i, last) + 1);
  }
  cout << gett(1, 1, n, 1, n) << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:142:9: warning: unused variable 'bigger' [-Wunused-variable]
  142 |     int bigger = 0;
      |         ^~~~~~

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