Submission #1173784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173784		Zero_OP	Financial Report (JOI21_financial)	C++20	100 / 100	400 ms	22608 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ull = unsigned long long;
using ld = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vc = vector<char>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

using vvi = vector<vi>;
using vvl = vector<vl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

struct SegmentTreeLIS{
      vi st;
      SegmentTreeLIS(int n)  { st.resize(4 * n, 0); }

      void update(int id, int l, int r, int pos, int val){
            if(l == r){
                  if(val == -1) st[id] = 0;
                  else maximize(st[id], val);
            } else{
                  int mid = l + r >> 1;
                  if(pos <= mid) update(id << 1, l, mid, pos, val);
                  else update(id << 1 | 1, mid + 1, r, pos, val);
                  st[id] = max(st[id << 1], st[id << 1 | 1]);
            }
      }

      int query(int id, int l, int r, int u, int v){
            if(v < l || u > r) return 0;
            if(u <= l && r <= v) return st[id];
            int mid = l + r >> 1;
            return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
      }

      void debug(int id, int l, int r){
            if(l == r){
                  cout << st[id] << ' ';
            } else{
                  int mid = l + r >> 1;
                  debug(id << 1, l, mid);
                  debug(id << 1 | 1, mid + 1, r);
            }
      }
};

const int inf = 1e9 + 9;
struct SegmentTreeMin{
      vpi min_occ; vi lazy;
      SegmentTreeMin(int n) : lazy(n << 2, -1), min_occ(n << 2, mp(inf, -1)) {}

      void apply(int id, int val){
            maximize(min_occ[id].ff, val);
            maximize(lazy[id], val);
      }

      void push(int id){
            if(lazy[id] != -1){
                  apply(id << 1, lazy[id]);
                  apply(id << 1 | 1, lazy[id]);
                  lazy[id] = -1;
            }
      }

      void insert(int id, int l, int r, int pos, int val){
            if(l == r){
                  min_occ[id] = mp(val, l);
            } else{
                  int mid = l + r >> 1;
                  push(id);
                  if(pos <= mid) insert(id << 1, l, mid, pos, val);
                  else insert(id << 1 | 1, mid + 1, r, pos, val);
                  min_occ[id] = min(min_occ[id << 1], min_occ[id << 1 | 1]);
            }
      }

      void erase(int id, int l, int r, int pos){
            if(l == r){
                  min_occ[id] = mp(inf, l);
            } else{
                  int mid = l + r >> 1;
                  push(id);
                  if(pos <= mid) erase(id << 1, l, mid, pos);
                  else erase(id << 1 | 1, mid + 1, r, pos);
                  min_occ[id] = min(min_occ[id << 1], min_occ[id << 1 | 1]);
            }
      }

      void update(int id, int l, int r, int u, int v, int tm){
            if(u <= l && r <= v) apply(id, tm);
            else{
                  int mid = l + r >> 1;
                  push(id);
                  if(u <= mid) update(id << 1, l, mid, u, v, tm);
                  if(mid < v)  update(id << 1 | 1, mid + 1, r, u, v, tm);
                  min_occ[id] = min(min_occ[id << 1], min_occ[id << 1 | 1]);
            }
      }
};

int main(){
      setIO();

      int N, D;
      cin >> N >> D;
      vi A(N), v;
      FOR(i, 0, N) cin >> A[i];

      v = A;
      sort(all(v)); compact(v);

      vi dp(N);
      SegmentTreeMin Tmin(sz(v));
      SegmentTreeLIS Tlis(sz(v));

      FOR(i, 0, N){
            A[i] = lower_bound(all(v), A[i]) - v.begin();
            if(i >= D+1){
                  while(i - Tmin.min_occ[1].ff > D){
                        int pos = Tmin.min_occ[1].ss;
                        Tlis.update(1, 0, sz(v)-1, pos, -1);
                        Tmin.erase(1, 0, sz(v)-1, pos);
//                        cout << dbg(pos) << '\n';
                  }
//                  Tlis.debug(1, 0, sz(v)-1); cout << '\n';
            }

            int dp = Tlis.query(1, 0, sz(v)-1, 0, A[i]-1) + 1;
            Tmin.update(1, 0, sz(v)-1, A[i], sz(v)-1,i);
            Tlis.update(1, 0, sz(v)-1, A[i], dp);
            Tmin.insert(1, 0, sz(v)-1, A[i], i);
//            cout << dp << " \n"[i == N-1];
//            Tlis.debug(1, 0, sz(v)-1);
//            cout << '\n';
      }

//      Tlis.debug(1, 0, sz(v)-1);
      cout << Tlis.st[1] << '\n';

      return 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