Submission #786939

#	Time	Username	Problem	Language	Result	Execution time	Memory
786939		gun_gan	Global Warming (CEOI18_glo)	C++17	0 / 100	216 ms	11184 KiB

glo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 2e5 + 5, inf = 1e9;

int N, X;
int a[MX], dp[MX], id[MX], rdp[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));
      }
} st, tt;

vector<pair<int, int>> v;

int getLow(int x) {
      auto it = lower_bound(v.begin(), v.end(), make_pair(x, -inf));
      return it - v.begin() + 1;
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N >> X;
      
      for(int i = 1; i <= N; i++) {
            cin >> a[i];
            v.push_back({a[i], i});
      }
      sort(v.begin(), v.end());

      int cnt = 1;
      for(auto [x, p] : v) id[p] = cnt++;

      for(int i = 1; i <= N; i++) {
            dp[i] = st.query(1, 1, N, 1, id[i]) + 1;
            st.update(1, 1, N, id[i], dp[i]);
      }

      for(int i = N; i >= 1; i--) {
            rdp[i] = tt.query(1, 1, N, id[i], N) + 1;
            tt.update(1, 1, N, id[i], rdp[i]);
      }

      int ans = 0;
      for(int i = 1; i <= N; i++) {
            tt.update(1, 1, N, id[i], 0);

            ans = max(ans, dp[i] + tt.query(1, 1, N, getLow(a[i] - X + 1), N));
      }

      cout << ans << '\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25