Submission #1066870

#TimeUsernameProblemLanguageResultExecution timeMemory
1066870Namviet2704Global Warming (CEOI18_glo)C++17
100 / 100
805 ms159680 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 2; int n, x, a[N]; int nNode; int ver[N]; struct node { int left, right; int ln; node () {} node(int ln, int left, int right) : ln(ln), left(left), right(right) {} } it[20000000], it1[20000000]; inline void refine(int cur) { it[cur].ln = max(it[it[cur].left].ln, it[it[cur].right].ln); } int update(int oldId, int l, int r, int u, int val) { if(l == r) { ++nNode; it[nNode] = node(max(it[oldId].ln, val), 0, 0); return nNode; } int mid = (l + r) >> 1; int cur = ++nNode; if(u <= mid) { it[cur].left = update(it[oldId].left, l, mid, u, val); it[cur].right = it[oldId].right; } else { it[cur].right = update(it[oldId].right, mid + 1, r, u, val); it[cur].left = it[oldId].left; } refine(cur); return cur; } int get(int nodeId, int l, int r, int u, int v) { if (v < l || r < u) return -1; if (u <= l && r <= v) return it[nodeId].ln; int mid = (l + r) >> 1; return max(get(it[nodeId].left, l, mid, u, v), get(it[nodeId].right, mid + 1, r, u, v)); } inline void refine1(int cur) { it1[cur].ln = max(it1[it1[cur].left].ln, it1[it1[cur].right].ln); } int update1(int oldId, int l, int r, int u, int val) { if(l == r) { ++nNode; it1[nNode] = node(max(it1[oldId].ln, val), 0, 0); return nNode; } int mid = (l + r) >> 1; int cur = ++nNode; if(u <= mid) { it1[cur].left = update(it1[oldId].left, l, mid, u, val); it1[cur].right = it1[oldId].right; } else { it1[cur].right = update(it1[oldId].right, mid + 1, r, u, val); it1[cur].left = it1[oldId].left; } refine1(cur); return cur; } int get1(int nodeId, int l, int r, int u, int v) { if (v < l || r < u) return -1; if (u <= l && r <= v) return it1[nodeId].ln; int mid = (l + r) >> 1; return max(get(it1[nodeId].left, l, mid, u, v), get(it1[nodeId].right, mid + 1, r, u, v)); } int st[12 * N]; void build(int id, int l, int r) { if(l == r) { st[id] = 0; return; } int mid = (l + r) >> 1; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); st[id] = 0; } void upd(int id, int l, int r, int u, int v) { if(l == r) { st[id] = max(st[id], v); return; } int mid = (l + r) >> 1; if(u <= mid) upd(id * 2, l, mid, u, v); else upd(id * 2 + 1, mid + 1, r, u, v); st[id] = max(st[id * 2], st[id * 2 + 1]); } int gett(int nodeId, int l, int r, int u, int v) { if (v < l || r < u) return -1; if (u <= l && r <= v) return st[nodeId]; int mid = (l + r) >> 1; return max(gett(nodeId * 2, l, mid, u, v), gett(nodeId * 2 + 1, mid + 1, r, u, v)); } int main () { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> x; vector<int> nen; nen.push_back(-1e9); nen.push_back(1e9); for(int i = 1; i <= n; i++) { cin >> a[i]; nen.push_back(a[i]); nen.push_back(a[i] + x); nen.push_back(a[i] - x); } sort(nen.begin(), nen.end()); nen.erase(unique(nen.begin(), nen.end()), nen.end()); int m = nen.size(); for(int i = n; i >= 1; i--) { int l = upper_bound(nen.begin(), nen.end(), a[i]) - nen.begin(); int tmp = get(ver[i + 1], 1, m, l + 1, m); // cout << tmp << '\n'; ver[i] = update(ver[i + 1], 1, m, l, tmp + 1); // cout << i << " " << l << " " << tmp + 1 << '\n'; } int ans = it[ver[1]].ln; for(int i = 1; i <= n; i++) { int r = upper_bound(nen.begin(), nen.end(), a[i]) - nen.begin(), l = upper_bound(nen.begin(), nen.end(), a[i] - x) - nen.begin(); int tmp = gett(1, 1, m, 1, r - 1); // cout << tmp << " " << get(ver[i + 1], 1, m, l + 1, m) << " " << l << " " << m << "huhu\n"; ans = max(ans, tmp + 1 + get(ver[i + 1], 1, m, l + 1, m)); upd(1, 1, m, r, tmp + 1); } build(1, 1, m); memset(ver, 0, sizeof ver); for(int i = 1; i <= n; i++) { int l = upper_bound(nen.begin(), nen.end(), a[i]) - nen.begin(); int tmp = get1(ver[i - 1], 1, m, 1, l - 1); // cout << tmp << '\n'; ver[i] = update1(ver[i - 1], 1, m, l, tmp + 1); // cout << i << " " << l << " " << tmp + 1 << '\n'; } for(int i = n; i >= 1; i--) { int l = upper_bound(nen.begin(), nen.end(), a[i]) - nen.begin(), r = upper_bound(nen.begin(), nen.end(), a[i] + x) - nen.begin(); int tmp = gett(1, 1, m, l + 1, m); // cout << tmp << " " << get(ver[i + 1], 1, m, l + 1, m) << " " << l << " " << m << "huhu\n"; ans = max(ans, tmp + 1 + get1(ver[i - 1], 1, m, 1, r - 1)); upd(1, 1, m, l, tmp + 1); } cout << ans; return 0; }

Compilation message (stderr)

glo.cpp: In constructor 'node::node(int, int, int)':
glo.cpp:14:9: warning: 'node::ln' will be initialized after [-Wreorder]
   14 |     int ln;
      |         ^~
glo.cpp:13:9: warning:   'int node::left' [-Wreorder]
   13 |     int left, right;
      |         ^~~~
glo.cpp:16:5: warning:   when initialized here [-Wreorder]
   16 |     node(int ln, int left, int right) : ln(ln), left(left), right(right) {}
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...