Submission #1031582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031582		orcslop	Global Warming (CEOI18_glo)	C++17	100 / 100	247 ms	45496 KiB

glo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

struct chash {
    const uint64_t C = uint64_t(6283185307179586476) + 71;
    const uint32_t RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    size_t operator()(uint64_t x) const {
        return __builtin_bswap64((x ^ RANDOM) * C);
    }
};

template <class K, class V> using ht = gp_hash_table
<K, V, /*hash<K> for undefined chash*/ chash, 
equal_to<K>, direct_mask_range_hashing<>, linear_probe_fn<>,
hash_standard_resize_policy<hash_exponential_size_policy<>,
hash_load_check_resize_trigger<>, true>>;

template <class T> class segtree {
  private:
    const T DEFAULT = 0;
    vector<T> tree;
    int n;

  public:
    segtree(int n) : n(n), tree(n * 2, DEFAULT) {}

    void reset(){
        tree = vector<int> (2 * n, DEFAULT); 
    }

    void update(int k, T val) {
        k += n;
        tree[k] = val; 
        for (k /= 2; k >= 1; k /= 2) {
            tree[k] = max(tree[2 * k], tree[2 * k + 1]); 
        }
    }

    T query(int a, int b) {
        T s = DEFAULT;
        for (a += n, b += n; a <= b; a /= 2, b /= 2) {
            if (a % 2 == 1) { s = max(s, tree[a++]); }
            if (b % 2 == 0) { s = max(s, tree[b--]); }
        }
        return s;
    }
};

const int MAXN = 2e5 + 5; 

int n, d; 
int v[MAXN]; 
int ps[MAXN]; 
int ss[MAXN]; 
vector<int> cc; 
ht<int, int> mp; 

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> d; 
    for(int i = 0; i < n; i++){
        cin >> v[i]; 
        cc.pb(v[i]); 
        cc.pb(v[i] - d); 
        cc.pb(v[i] + d); 
    }
    sort(all(cc)); 
    cc.erase(unique(all(cc)), cc.end()); 
    for(int i = 0; i < sz(cc); i++){
        mp[cc[i]] = i; 
    }
    segtree<int> tree(sz(cc) + 2); 
    for(int i = 0; i < n; i++){
        int curr = mp[v[i]]; 
        ps[i] = tree.query(0, curr - 1) + 1; 
        if(tree.query(curr, curr) < ps[i]) {
            tree.update(curr, ps[i]); 
        }
    }
    tree.reset(); 
    for(int i = n - 1; i >= 0; i--){
        int curr = mp[v[i]]; 
        ss[i] = tree.query(curr + 1, sz(cc) - 1) + 1; 
        if(tree.query(curr, curr) < ss[i]){
            tree.update(curr, ss[i]); 
        }
    }
    tree.reset(); 
    int ans = 0; 
    for(int i = n - 1; i >= 0; i--){
        ans = max(ans, ps[i] + tree.query(mp[v[i] - d] + 1, sz(cc) - 1)); 
        if(tree.query(mp[v[i]], mp[v[i]]) < ss[i]){
            tree.update(mp[v[i]], ss[i]); 
        }
    }
    cout << ans << '\n'; 
    // for(int i = 0; i < n; i++){
        // cout << ss[i] << ' '; 
    // }    
    return 0; 
}

Compilation message (stderr)

glo.cpp: In instantiation of 'segtree<T>::segtree(int) [with T = int]':
glo.cpp:78:33:   required from here
glo.cpp:28:9: warning: 'segtree<int>::n' will be initialized after [-Wreorder]
   28 |     int n;
      |         ^
glo.cpp:27:15: warning:   'std::vector<int> segtree<int>::tree' [-Wreorder]
   27 |     vector<T> tree;
      |               ^~~~
glo.cpp:31:5: warning:   when initialized here [-Wreorder]
   31 |     segtree(int n) : n(n), tree(n * 2, DEFAULT) {}
      |     ^~~~~~~

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