Submission #1128670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128670		VinhLuu	Financial Report (JOI21_financial)	C++17	19 / 100	204 ms	26276 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;

  for(int k = 1; k <= (int)rrh.size(); k ++) {
    for(auto j : col[k]) {
      int pos = val[fin(j)];
//      cerr << j << " " << pos << " " << get(pos, j) << " g\n";
      f[j] = max(get(pos, j) + 1, 1);
      ans = max(ans, f[j]);
    }
    for(auto j : col[k]) {
      update(j, f[j]);
      query(max(1, j - m), min(n, j + m));
    }
  }

  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: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35