제출 #564554

#제출 시각아이디문제언어결과실행 시간메모리
564554nikatamlianiFinancial Report (JOI21_financial)C++14
48 / 100
4094 ms40904 KiB
#include <bits/stdc++.h> using namespace std; const int N = 3e5+10; 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; } } vector<int> ids[N], to_delete[N]; int n, d; int a[N], on[N], rgh[N], p[N], s[N], dp[N], t[4 * N]; 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]; } void update(int l, int r, int x, int v, int pos) { if (l > x || r < x) { return; } if (l == r) { t[pos] = v; } else { int m = l + r >> 1; update(l, m, x, v, pos << 1); update(m+1, r, x, v, pos << 1 | 1); t[pos] = max(t[pos << 1], t[pos << 1 | 1]); } } void update(int id, int v) { update(1, n, id, v, 1); } int query(int l, int r, int L, int R, int pos) { if (L > r || l > R) return 0; if (L <= l && R >= r) { return t[pos]; } int m = l + r >> 1; return max(query(l, m, L, R, pos << 1), query(m + 1, r, L, R, pos << 1 | 1)); } int query(int l, int r) { return query(1, n, l, r, 1); } multiset<int> m[N]; void del(int id, int v) { m[id].erase(m[id].find(v)); } void ins(int id, int v) { m[id].insert(v); } int get(int id) { if (!m[id].empty()) { return *m[id].rbegin(); } return 0; } 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) { to_delete[rgh[i]].push_back(i); } int best = 0; rgh[0] = n; for (int i = 1; i <= n; ++i) { // dp[i] = query(1, a[i] - 1) + 1; // ins(a[i], dp[i]); // update(a[i], get(a[i])); // for (int id : to_delete[i]) { // del(a[id], dp[id]); // update(id, get(a[id])); // } 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 'void update(int, int, int, int, int)':
Main.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'int query(int, int, int, int, int)':
Main.cpp:55:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int m = 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...