Submission #831265

#	Time	Username	Problem	Language	Result	Execution time	Memory
831265		perchuts	Financial Report (JOI21_financial)	C++17	100 / 100	791 ms	63064 KiB

Main

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int ll

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

ii seg[4*maxn];

int n, d;

vector<int> events[maxn];

int lis[4*maxn];

void update(int i, int l, int r, int x, int k) {
      if (r < x || x < l) return;
      if (l == r) {
            seg[i] = {k, l}; return;
      }
      int md = (l + r) / 2;
      update(2*i, l, md, x, k), update(2*i+1, md+1, r, x, k);
      if (seg[2*i].first >= d) seg[i] = seg[2*i];
      else seg[i] = max(seg[2*i], seg[2*i+1]);
}

ii query(int i, int l, int r, int x, int y = n) {
      if (r < x || y < l) return {0, 0};
      if (x <= l && r <= y) return seg[i];
      int md = (l + r) / 2;
      ii lx = query(2*i, l, md, x, y), rx = query(2*i+1, md+1, r, x, y);
      if (lx.first >= d) return lx;
      return max(lx, rx);
}


void upd(int i, int l, int r, int x, int k) {
      if (x < l || r < x) return;
      if (l == r) {
            lis[i] = k; return;
      }
      int md = (l + r) / 2;
      upd(2*i, l, md, x, k), upd(2*i+1, md+1, r, x, k);
      lis[i] = max(lis[2*i], lis[2*i+1]);
}

int queryLis(int i, int l, int r, int x, int y) {
      if (r < x || y < l || x > y) return 0;
      if (x <= l && r <= y) return lis[i];
      int md = (l + r) / 2;
      return max(queryLis(2*i, l, md, x, y), queryLis(2*i+1, md+1, r, x, y));
}

int32_t main(){_

      cin >> n >> d;

      vector<int> v(n+1); 

      for (int i = 0; i < n; ++i) cin >> v[i];

      vector<int> ord(n); iota(all(ord), 0); 

      sort(all(ord), [&] (int x, int y) {return (v[x] == v[y] ? x > y : v[x] < v[y]);});
      ord.pb(n);

      set<int> inserted;
      
      vector<int> equal;

      int cur = v[ord[0]];

      for (auto id : ord) {
            id++;
            
            if (v[id - 1] != cur) {
                  for (auto x : equal) {
                        ii q = query(1, 1, n, x);
                        if (q.first >= d) {
                              // cout << x << " vai ser removido em " << q.second + d + 1 << endl;
                              events[q.second + d + 1].pb(x);
                        }
                  }

                  cur = v[id - 1], equal = {id};

            } else equal.pb(id);

            if (id == n + 1) break;

            auto it = inserted.lower_bound(id);

            if (it != begin(inserted)) {
                  it = prev(it);
                  int y = *it;
                  update(1, 1, n, y, id - y - 1), it = next(it);
            }

            int z;

            if (it == end(inserted)) z = n - id;
            else z = *it - id - 1;

            update(1, 1, n, id, z), inserted.insert(id);
      }     

      for (int i = 0; i < n; ++i) v[ord[i]] = i + 1; 

      int ans = 0;

      for (int i = 1; i <= n; ++i) {
            for (auto x : events[i]) {
                  // cout << "- " << x << endl;
                  upd(1, 1, n, v[x-1], 0);
            }
            int best = queryLis(1, 1, n, 1, v[i-1] - 1) + 1;
            ckmax(ans, best);
            // cout << "answer for " << i << ": " << best << endl;
            upd(1, 1, n, v[i-1], best);
            // cout << "+ " << i << ' ' << v[i-1] << ' ' << best << endl;
      }
      
      cout << ans << endl;
}

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