Submission #1128731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128731		VinhLuu	Financial Report (JOI21_financial)	C++17	100 / 100	485 ms	40344 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

#define lpv

#ifndef lpv
#include "AC.h"
#endif // lpv

//#define int long long

const int N = 3e5 + 5;
const int oo = -1e9;

int n, m, a[N], st[N << 1];
vector<int> rrh;

void update(int i,int val) {
  i += n - 1;
  st[i] = max(st[i], val);
  while(i > 1) {
    i /= 2;
    st[i] = max(st[i], val);
  }
}
int get(int l,int r) {
  if(l > r) return oo;
  r++;
  int ret = oo;
  for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2) {
    if(l & 1) ret = max(ret, st[l ++]);
    if(r & 1) ret = max(ret, st[-- r]);
  }
  return ret;
}

vector<int> col[N];
int f[N], ans = 0, pa[N], sz[N], val[N];

int fin(int u) {
  return pa[u] == u ? u : pa[u] = fin(pa[u]);
}

void dsu(int x,int y) {
  x = fin(x);
  y = fin(y);
  if(x == y) return;
  if(sz[x] < sz[y]) swap(x, y);
  sz[x] += sz[y];
  pa[y] = x;
  val[x] = min(val[x], val[y]);
}

void query(int l,int r) {
  while(val[fin(r)] - 1 >= l) {
    dsu(val[fin(r)] - 1, r);
    r = val[fin(r)];
  }
}

#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> m;
  for(int i = 1; i <= n; i ++) {
    cin >> a[i];
    rrh.push_back(a[i]);
  }

  sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());

  for(int i = 1; i <= n; i ++) {
    pa[i] = i, sz[i] = 1, val[i] = i;
    a[i] = lower_bound(all(rrh), a[i]) - rrh.begin() + 1;
    col[a[i]].push_back(i);
  }

  for(int i = 1; i <= 2 * n; i ++) st[i] = oo;

  set<int> ver;

  for(int k = 1; k <= (int)rrh.size(); k ++) {
    for(auto j : col[k]) {
      auto ptr = ver.upper_bound(j);
      if(ptr != ver.begin()) {
        ptr--;
        if((*ptr) >= j - m) {
          int pos = val[fin((*ptr))];
//          cerr << j << " " << pos << " " << get(pos, j) << " t\n";
          f[j] = max(1, get(pos, j) + 1);
        } else f[j] = 1;
      } else f[j] = 1;
      ans = max(ans, f[j]);
    }
    for(auto j : col[k]) {
      update(j, f[j]);
      ver.insert(j);
//      cerr << k << " " << j << " " << f[j] << " " << max(1, j - m) << " " << j << " g\n";
      query(max(1, j - m), j);
    }
  }

  cout << ans << "\n";

}

#endif // lpv

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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