Submission #882150

#	Time	Username	Problem	Language	Result	Execution time	Memory
882150		skywwla	Global Warming (CEOI18_glo)	C++17	38 / 100	2054 ms	24748 KiB

glo

#include <bits/stdc++.h>

using namespace std ;
using ll = long long ;

struct SegTree {
   int _n ;
   struct Node {
      ll value = 0 ;
      Node() {}
      Node(ll x) {
         value = x ;
      }
   };
   Node combine(Node l, Node r) {
      if (l.value > r.value) return l ;
      return r ;
   }
   vector<Node> t ;
   SegTree(int len) {
      _n = len ;
      t.assign(len * 4 + 1, Node(0)) ;
   }
   void modify(int i, ll x, int v, int tl, int tr) {
      if (tl == tr) {
         t[v] = combine(x, t[v]) ;
      } else {
         int tm = (tl + tr) >> 1 ;
         if (i <= tm)
            modify(i, x, v << 1, tl, tm) ;
         else
            modify(i, x, v << 1 | 1, tm + 1, tr) ;
         t[v] = combine(t[v * 2], t[v * 2 + 1]) ;
      }
   }
   void modify(int i, ll x) {
      modify(i, x, 1, 1, _n) ;
   }
   Node get(int l, int r, int v, int tl, int tr) {
      if (l > tr || r < tl) return Node(0) ;
      if (l <= tl && tr <= r) return t[v] ;
      int tm = (tl + tr) >> 1 ;
      Node L = get(l, r, v << 1, tl, tm) ;
      Node R = get(l ,r, v << 1 | 1, tm + 1, tr) ;
      return combine(L, R) ;
   }
   Node get(int l, int r) {
       if (l > r) return Node(0) ;
      return get(l, r, 1, 1, _n) ;
   }
};

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    int n , x ;
    cin >> n >> x ;
    vector<int> a(n + 1), c ;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i] ;
        c.push_back(a[i]) ;
        c.push_back(a[i] - 1) ;
        c.push_back(a[i] + 1) ;
    }
    sort(c.begin(), c.end()) ;
    c.erase(unique(c.begin(), c.end()), c.end()) ;
    auto get = [&](int i) -> int {
        return (lower_bound(c.begin(), c.end(), i) - c.begin() + 1) ;
    };
    int m = c.size() ;
    SegTree s(m) ;
    int ret = 0 ;
    vector<int> pre(n + 1, 1), suf(n + 1, 1) ;
    for (int i = 1 ; i <= n ; i++) {
        pre[i] = max(pre[i] * 1ll, s.get(1, get(a[i] - 1)).value + 1) ;
        s.modify(get(a[i]), pre[i]) ;
        ret = max(ret, pre[i]) ;
    }
    if (!x) {
        cout << ret ;
        return 0 ;
    }
    s = SegTree(m) ;
    for (int i = n ; i >= 1 ; i--) {
        suf[i] = max(suf[i] * 1ll, s.get(get(a[i] + 1), m).value + 1) ;
        s.modify(get(a[i]), suf[i]) ;
    }
    for (int i = 1 ; i <= n ; i++) {
        for (int j = i + 1 ; j <= n ; j++) {
            if (a[j] - 1 >= a[i] - x && a[j] - 1 <= a[i] + x) {
                ret = max(ret, pre[i] + suf[j]) ;
            }
        }
        ret = max(ret, pre[i]) ;
    }
    cout << ret ;
    return 0 ;
}

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