Submission #486024

#TimeUsernameProblemLanguageResultExecution timeMemory
486024Duy_eRabbit Carrot (LMIO19_triusis)C++14
0 / 100
0 ms332 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define pii pair<long long, long long> #define st first #define nd second #define file "test" using namespace std; const long long oo = 1e18; const long long N = 2e5 + 5; int n, m, a[N], dp[N], bit[2*N]; int SIZE; vector <int> compress; void upd(int idx, int val){ while (idx > 0) bit[idx] = max(bit[idx], val), idx -= idx & -idx; } int get(int idx, int ans = 0){ while (idx <= SIZE) ans = max(bit[idx], ans), idx += idx & -idx; return ans; } int find(int x){ int l = 0, r = compress.size() - 1, mid, ans = 0; while (l <= r){ mid = l + r >> 1; if (compress[mid] >= x) ans = mid + 1, r = mid - 1; else l = mid + 1; } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // #ifndef ONLINE_JUDGE // freopen(file".inp","r",stdin); freopen(file".out","w",stdout); // #endif cin >> n >> m; compress.push_back(0); // current standing compress.push_back(0 + m); // current standing for (int i = 1; i <= n; i ++){ cin >> a[i]; compress.push_back(a[i]); compress.push_back(max(0, a[i] - m)); } // cordinate compression sort(compress.begin(), compress.end()); compress.resize(unique(compress.begin(), compress.end()) - compress.begin()); SIZE = compress.size() + 100; // -> erase duplicate elements // PROCESS: key idea -> finding longest possible path = L -> ans = n - L for (int i = 1; i <= SIZE; i ++) bit[i] = -1e9; upd(find(0), 1); for (int i = 1; i <= n; i ++){ int cur = find(max(0, a[i] - m)); ll tmp = get(cur) + 1; if (tmp == 1) continue; upd(find(a[i]), tmp); } cout << n - get(1) + 1; return 0; } /** /\_/\ (= ._.) / >0 \>1 ________________________ / Brainstorming section / /=======================/ --- === === **/ // Before submit: spot the visible bug by reading the code.

Compilation message (stderr)

triusis.cpp: In function 'int find(int)':
triusis.cpp:33:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   mid = l + r >> 1;
      |         ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...