Submission #1244011

#TimeUsernameProblemLanguageResultExecution timeMemory
1244011HishamAlshehriFinancial Report (JOI21_financial)C++20
5 / 100
531 ms26592 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> using namespace std; // using namespace __gnu_pbds; #define int long long #define mod 1000000007 #define base 7001 #define base2 757 #define F first #define S second // #define pi acos(-1) #define double long double // #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> // #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> // #pragma GCC optimize("O3,Ofast,unroll-loops") // #pragma GCC target("avx2,sse3,sse4,avx") mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); constexpr int maxn = 1000005; const int N = 1 << (int)(ceil(log2(maxn))); int n, d, a[maxn], l, r, tree[2 * N + 5]; bool b[maxn]; int q(int ql, int qr, int i) { if (ql >= l && qr <= r) return tree[i]; if (ql > r || qr < l) return 0; return max(q(ql, (ql + qr) / 2, i * 2), q((ql + qr) / 2 + 1, qr, i * 2 + 1)); } void u(int i) { while (i /= 2) tree[i] = max(tree[i * 2], tree[i * 2 + 1]); } void compress() { map<int, int> mp; for (int i = 0; i < n; i++) mp[a[i]] = 1; int cnt = 0; for (auto [i, j] : mp) if (j != NULL) mp[i] = cnt++; for (int i = 0; i < n; i++) a[i] = mp[a[i]]; } signed main() { cin.tie(0) -> sync_with_stdio(0); cin >> n >> d; for (int i = 0; i < n; i++) cin >> a[i]; compress(); int curl = 0, mxl = 0, ans = 0; multiset<bool> s; for (int i = 0; i < n; i++) { if (s.size() && !(*s.begin())) mxl = i - d; if (curl < mxl) { while (curl < i - d) { tree[a[curl] + N] = 0; u(a[curl] + N); curl++; } } l = 0, r = a[i] - 1; int cur = q(0, N - 1, 1) + 1; l = a[i], r = N; if (q(0, N - 1, 1)) b[i] = 1; if (i >= d) { s.extract(b[i - d]); s.insert(b[i]); } ans = max(cur, ans); tree[a[i] + N] = cur; u(a[i] + N); // cout << cur << ' ' << curl << ' ' << b[i] << ' ' << a[i] << '\n'; } cout << ans; }

Compilation message (stderr)

Main.cpp: In function 'void compress()':
Main.cpp:45:37: warning: NULL used in arithmetic [-Wpointer-arith]
   45 |     for (auto [i, j] : mp) if (j != NULL) mp[i] = cnt++;
      |                                     ^~~~
#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...