Submission #678135

#TimeUsernameProblemLanguageResultExecution timeMemory
678135Tien_NoobFinancial Report (JOI21_financial)C++17
5 / 100
682 ms77308 KiB
//Make CSP great again //Vengeance #include <bits/stdc++.h> #define TASK "TESTCODE" using namespace std; const int N = 3e5 + 1; int a[N + 1], b[N + 1], dp[N + 1], d, n; vector<int> f[N + 1]; set<int> s; int lab[N + 1], mx[N + 1]; int FindSet(int u) { return lab[u] < 0 ? u : lab[u] = FindSet(lab[u]); } void unite(int u, int v) { u = FindSet(u); v = FindSet(v); if (u == v) { return ; } if (lab[u] > lab[v]) { swap(u, v); } lab[u] += lab[v]; lab[v] = u; mx[u] = max(mx[u], mx[v]); } struct SegmentTree { int tree[4 * N + 1]; void upd(int v, int TreeL, int TreeR, int pos, int val) { if (TreeL == TreeR) { tree[v] = val; return ; } int mid = (TreeL + TreeR)/2; if (pos <= mid) { upd(v * 2, TreeL, mid, pos, val); } else { upd(v * 2 + 1, mid + 1, TreeR, pos, val); } tree[v] = max(tree[2 * v], tree[2 * v + 1]); } int get(int v, int TreeL, int TreeR, int L, int R) { if (L > R) { return 0; } if (TreeL == L && TreeR == R) { return tree[v]; } int mid = (TreeL + TreeR)/2; return max(get(v * 2, TreeL, mid, L, min(R, mid)), get(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R)); } } tree; void read() { cin >> n >> d; for (int i = 1; i <= n; ++ i) { cin >> a[i]; b[i] = a[i]; } memset(lab, -1, sizeof(lab)); iota(mx, mx + n + 2, 0); sort(b + 1, b + n + 1); for (int i = 1; i <= n; ++ i) { a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b; f[a[i]].push_back(i); } } vector<int> del[N + 1]; multiset<int> val[N + 1]; void solve() { s.insert(0); s.insert(n + 1); for (int i = 1; i <= n; ++ i) { while(!f[i].empty()) { int j = f[i].back(); f[i].pop_back(); auto it = s.lower_bound(j); --it; int pre = *it; ++it; ++it; int nxt = *it; if (pre + d >= j) { unite(pre, j); } if (j + d <= nxt) { unite(j, nxt); } del[min(n, mx[FindSet(j)] + d)].push_back(j); s.insert(j); } } int res = 0; for (int i = 1; i <= n; ++ i) { dp[i] = tree.get(1, 1, n, 1, a[i] - 1) + 1; val[a[i]].insert(dp[i]); tree.upd(1, 1, n, a[i], *val[a[i]].rbegin()); for (int j : del[i]) { val[a[j]].erase(val[a[j]].find(dp[j])); tree.upd(1, 1, n, a[j], val[a[j]].empty() ? 0 : *val[a[j]].rbegin()); } res = max(res, dp[i]); } cout << res; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); //freopen(TASK".OUT", "w", stdout); } int t = 1; bool typetest = false; if (typetest) { cin >> t; } for (int __ = 1; __ <= t; ++ __) { //cout << "Case " << __ << ": "; read(); solve(); } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...