# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
881914 | 2023-12-02T08:52:00 Z | deadeye0 | Financial Report (JOI21_financial) | C++17 | 708 ms | 101400 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define fi first #define si second #define ar array #define pb push_back typedef pair<int,int> pi; typedef tuple<int,int,int> ti; typedef vector<int> vi; template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;} template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;} void debug_out() {cerr<<endl;} template <typename Head, typename... Tail> void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);} #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) const int N = 300010; int n, d, ans; int a[N], dp[N]; struct node { node *l, *r; int val, s, m, e, lazyadd; bool upd; node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), upd(false), l(NULL), r(NULL) { if (s != e) l = new node(s, m), r = new node(m+1, e); } int value() { if (upd) { val = lazyadd; upd = false; if (s == e) return val; l->lazyadd = lazyadd; r->lazyadd = lazyadd; r->upd = true, l->upd = true; } return val; } void set(int x, int y, int v) { if (s == x && e == y) lazyadd = v, upd = true; else { if (x > m) r->set(x, y, v); else if (y <= m) l->set(x, y, v); else l->set(x, m, v), r->set(m+1, y, v); val = max(l->value(), r->value()); } } int query(int x, int y) { value(); if (s == x && e == y) return value(); if (x > m) return r->query(x, y); if (y <= m) return l->query(x, y); return max(l->query(x, m),r->query(m+1, y)); } } *st, *active; signed main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin.exceptions(ios::badbit|ios::failbit); cin >> n >> d; vector<int> temp(n); for (int i = 0; i < n; ++i) { cin >> a[i]; temp[i] = a[i]; } sort(temp.begin(), temp.end()); temp.resize(unique(temp.begin(), temp.end()) - temp.begin()); for (int i = 0; i < n; ++i) { a[i] = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin(); } st = new node(0, n); active = new node(0, n); for (int i = 0; i < n; ++i) { if (i - d - 1 >= 0) { if (active->query(a[i - d - 1], a[i - d - 1]) < i - d) { st->set(a[i - d - 1], a[i - d - 1], 0); } } chmax(dp[a[i]], 1ll); if (a[i] > 0) chmax(dp[a[i]], st->query(0, a[i] - 1) + 1); if (st->query(a[i], a[i]) < dp[a[i]]) { st->set(a[i], a[i], dp[a[i]]); } active->set(a[i], n, i); chmax(ans, dp[a[i]]); } cout << ans; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2396 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 0 ms | 2396 KB | Output is correct |
5 | Correct | 0 ms | 2396 KB | Output is correct |
6 | Correct | 0 ms | 2396 KB | Output is correct |
7 | Correct | 0 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 0 ms | 2396 KB | Output is correct |
10 | Correct | 0 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 0 ms | 2396 KB | Output is correct |
13 | Correct | 0 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2392 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 0 ms | 2396 KB | Output is correct |
18 | Correct | 0 ms | 2396 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 1 ms | 2396 KB | Output is correct |
22 | Correct | 0 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2392 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 0 ms | 2396 KB | Output is correct |
26 | Correct | 0 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2396 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 0 ms | 2396 KB | Output is correct |
5 | Correct | 0 ms | 2396 KB | Output is correct |
6 | Correct | 0 ms | 2396 KB | Output is correct |
7 | Correct | 0 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 0 ms | 2396 KB | Output is correct |
10 | Correct | 0 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 0 ms | 2396 KB | Output is correct |
13 | Correct | 0 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2392 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 0 ms | 2396 KB | Output is correct |
18 | Correct | 0 ms | 2396 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 1 ms | 2396 KB | Output is correct |
22 | Correct | 0 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2392 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 0 ms | 2396 KB | Output is correct |
26 | Correct | 0 ms | 2396 KB | Output is correct |
27 | Incorrect | 1 ms | 2652 KB | Output isn't correct |
28 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2396 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 0 ms | 2396 KB | Output is correct |
5 | Correct | 0 ms | 2396 KB | Output is correct |
6 | Correct | 0 ms | 2396 KB | Output is correct |
7 | Correct | 0 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 0 ms | 2396 KB | Output is correct |
10 | Correct | 0 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 0 ms | 2396 KB | Output is correct |
13 | Correct | 0 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2392 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 0 ms | 2396 KB | Output is correct |
18 | Correct | 0 ms | 2396 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 1 ms | 2396 KB | Output is correct |
22 | Correct | 0 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2392 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 0 ms | 2396 KB | Output is correct |
26 | Correct | 0 ms | 2396 KB | Output is correct |
27 | Incorrect | 1 ms | 2652 KB | Output isn't correct |
28 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 112 ms | 99096 KB | Output is correct |
2 | Correct | 193 ms | 99152 KB | Output is correct |
3 | Incorrect | 223 ms | 99092 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 92 ms | 99156 KB | Output is correct |
2 | Correct | 171 ms | 98968 KB | Output is correct |
3 | Correct | 261 ms | 99156 KB | Output is correct |
4 | Correct | 708 ms | 101284 KB | Output is correct |
5 | Correct | 534 ms | 101208 KB | Output is correct |
6 | Correct | 674 ms | 101268 KB | Output is correct |
7 | Correct | 209 ms | 101400 KB | Output is correct |
8 | Correct | 210 ms | 101292 KB | Output is correct |
9 | Correct | 227 ms | 100684 KB | Output is correct |
10 | Correct | 341 ms | 100920 KB | Output is correct |
11 | Correct | 689 ms | 101200 KB | Output is correct |
12 | Correct | 608 ms | 101200 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2396 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 0 ms | 2396 KB | Output is correct |
5 | Correct | 0 ms | 2396 KB | Output is correct |
6 | Correct | 0 ms | 2396 KB | Output is correct |
7 | Correct | 0 ms | 2396 KB | Output is correct |
8 | Correct | 1 ms | 2396 KB | Output is correct |
9 | Correct | 0 ms | 2396 KB | Output is correct |
10 | Correct | 0 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 0 ms | 2396 KB | Output is correct |
13 | Correct | 0 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2392 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 0 ms | 2396 KB | Output is correct |
18 | Correct | 0 ms | 2396 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 1 ms | 2396 KB | Output is correct |
22 | Correct | 0 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2392 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 0 ms | 2396 KB | Output is correct |
26 | Correct | 0 ms | 2396 KB | Output is correct |
27 | Incorrect | 1 ms | 2652 KB | Output isn't correct |
28 | Halted | 0 ms | 0 KB | - |