제출 #564551

#제출 시각아이디문제언어결과실행 시간메모리
564551nikatamlianiFinancial Report (JOI21_financial)C++14
48 / 100
4058 ms17500 KiB
#include <bits/stdc++.h> using namespace std; const int N = 3e5+10; int n, d; int a[N], on[N], rgh[N], dp[N], p[N], s[N], t[4 * N]; vector<int> ids[N]; void compress(vector<int*> &v) { int prv = -1, cnt = 0; sort(v.begin(), v.end(), [&](int* a, int* b) { return *a < *b; }); for (int i = 0; i < (int)v.size(); ++i) { cnt += prv < *v[i]; prv = *v[i]; *v[i] = cnt; } } int find_set(int x) { return p[x] == x ? x : p[x] = find_set(p[x]); } void union_sets(int u, int v) { u = find_set(u); v = find_set(v); if (u == v) { return; } if (u > v) { swap(u, v); } p[v] = u; s[u] += s[v]; } int main() { cin >> n >> d; vector<int*> coords(n); for (int i = 1; i <= n; ++i) { p[i] = i; s[i] = 1; cin >> a[i]; coords[i - 1] = &a[i]; } compress(coords); for (int i = 1; i <= n; ++i) { ids[a[i]].push_back(i); } set<int> st = {n + 1}; for (int i = n; i >= 1; --i) { for (int id : ids[i]) { rgh[id] = min(*st.lower_bound(id) + d - 1, n); on[id] = 1; if (on[id + 1] == 1) { union_sets(id, id + 1); } if (on[id - 1] == 1) { union_sets(id, id - 1); } int u = find_set(id); if (s[u] >= d) { st.insert(u); } } } for (int i = 1; i <= n; ++i) { int count = 0, pos = i, rg = i; for (int j = i + 1; j <= n; ++j) { if (j - pos > d) break; if (a[j] <= a[i]) pos = j; rg = j; } // cout << rg << ' ' << rgh[i] << endl; // assert(rg == rgh[i]); } int best = 0; a[0] = -1; rgh[0] = n; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { if (rgh[j] >= i && a[j] < a[i]) { dp[i] = max(dp[i], dp[j] + 1); } } best = max(best, dp[i]); } cout << best << endl; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:70:13: warning: unused variable 'count' [-Wunused-variable]
   70 |         int count = 0, pos = i, rg = i;
      |             ^~~~~
Main.cpp:70:33: warning: variable 'rg' set but not used [-Wunused-but-set-variable]
   70 |         int count = 0, pos = i, rg = i;
      |                                 ^~
#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...