Submission #806746

#	Time	Username	Problem	Language	Result	Execution time	Memory
806746		gun_gan	Financial Report (JOI21_financial)	C++17	100 / 100	626 ms	26156 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MX = 3e5 + 5, inf = 1e9;
int N, D;
int a[MX], id[MX];
 
struct segtree {
      int t[4 * MX];
 
      void update(int v, int l, int r, int pos, int val) {
            if(l > pos || r < pos) return;
            if(l == r) {
                  t[v] = val;
                  return;
            }
            int mid = (l + r) >> 1;
            update(v * 2 + 0, l, mid + 0, pos, val);
            update(v * 2 + 1, mid + 1, r, pos, val);
            t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
      }
 
      int query(int v, int l, int r, int ql, int qr) {
            if(ql > r || qr < l) return 0;
            if(ql <= l && qr >= r) return t[v];
            int mid = (l + r) >> 1;
            return max(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
      }
} t;
 
vector<pair<int,int>> comp;
 
int getId(int x) { // find < x
      auto it = lower_bound(comp.begin(), comp.end(), make_pair(x, -inf));
      return it - comp.begin();
}
 
int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);
 
      cin >> N >> D;
 
      for(int i = 1; i <= N; i++) {
            cin >> a[i];
            comp.push_back({a[i], i});
      }
 
      comp.push_back({0, 0});
      sort(comp.begin(), comp.end());
 
      int p = 0;
      for(auto [x, pos] : comp) {
            id[pos] = p++;
      }
 
      set<pair<int,int>> st, tt; // last D + 1 elements, other elements before last D + 1
      int ans = 0;
      for(int i = 1; i <= N; i++) {
            while(!tt.empty()) {
                  if(tt.begin()->first < st.begin()->first) {
                        t.update(1, 0, p, id[tt.begin()->second], 0);
                        tt.erase(tt.begin());
                  } else {
                        break;
                  }
            }

            st.insert({a[i], i});
 
            int k = max(t.query(1, 0, p, 0, getId(a[i]) - 1) + 1, t.query(1, 0, p, 0, getId(a[i] + 1) - 1));
            ans = max(ans, k);
            t.update(1, 0, p, id[i], k);
            
            if(i - D >= 1) {
                  st.erase({a[i - D], i - D});
                  tt.insert({a[i - D], i - D});
            }
      }
 
      cout << ans << '\n';
}

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