Submission #1087018

#TimeUsernameProblemLanguageResultExecution timeMemory
1087018ccccFinancial Report (JOI21_financial)C++14
65 / 100
599 ms24456 KiB
/// YVKNTD #include <bits/stdc++.h> #define int long long #define ld long double #define f(i, a, b) for(int i = a; i <= b; i++) #define fr(i, a, b) for(int i = a; i >= b; i--) #define pii pair <int, int> #define fi first #define se second #define pb push_back #define eb emplace_back #define in insert #define vvec vector<vector<int>> #define Keiiiii ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ___ 1000 * clock() / CLOCKS_PER_SEC using namespace std; const int N = 3e5 + 5; const int mod = 1e9 + 7; const int inf = 1e16; int n, k, a[N]; void READ() { cin >> n >> k; f(i, 1, n) cin >> a[i]; } struct ST { int st[N * 4]; void up(int i, int l, int r, int j, int w) { if(j > r || j < l) return; if(l == r) { st[i] = w; return; } int mid = (l + r) >> 1; up(i << 1, l, mid, j, w); up(i << 1 | 1, mid + 1, r, j, w); st[i] = max(st[i << 1], st[i << 1 | 1]); } int get(int i, int l, int r, int x, int y) { if(x > r || y < l) return 0; if(x <= l && r <= y) return st[i]; int mid = (l + r) >> 1; return max(get(i << 1, l, mid, x, y), get(i << 1 | 1, mid + 1, r, x, y)); } } f, ff; void cmprss() { vector <int> z; f(i, 1, n) z.eb(a[i]); sort(z.begin(), z.end()); z.resize(unique(z.begin(), z.end()) - z.begin()); f(i, 1, n) a[i] = lower_bound(z.begin(), z.end(), a[i]) - z.begin() + 1; } int dp[N]; void sub3() { f(i, 1, n) { dp[i] = 1; int cnt = 0, mx = 0, ok = 1; fr(j, i - 1, 1) { mx = max(a[j], mx); if(a[j] >= a[i]) cnt++; else cnt = 0; if(cnt >= k) ok = 0; if(i - j <= k) { if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1); } else if(ok) { if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1); } //cerr << dp[i] << " " << i << "\n"; } } cout << *max_element(dp + 1, dp + n + 1) << "\n"; } void sub4() { vector <int> dp(n + 1, 1); f(i, 1, n) f.up(1, 1, n, i, a[i]); f(i, 1, n) { int l = 1, r = i - 1, j = i; while(l <= r) { int mid = (l + r) >> 1; if(f.get(1, 1, n, mid, i - 1) < a[i]) r = mid - 1, j = mid; else l = mid + 1; } //cerr << j << " " << i << "\n"; dp[i] = ff.get(1, 1, n, j, i - 1) + 1; ff.up(1, 1, n, i, dp[i]); } cout << *max_element(dp.begin(), dp.end()); } void sub5() { vector <int> ff(n + 1, inf); ff[0] = -inf; int ans = 1; f(i, 1, n) { int k = lower_bound(ff.begin(), ff.end(), a[i]) - ff.begin(); ff[k] = a[i]; ans = max(ans, k); } cout << ans << "\n"; } void SOLVE() { if(n <= 7000) sub3(); else if(k == 1) sub4(); else if(k == n) sub5(); else { k++; cmprss(); multiset <int> s; int ans = 0; f(i, 1, n) { if(i > k) { s.erase(s.find(a[i - k])); if(s.find(a[i - k]) == s.end()) f.up(1, 1, n, a[i - k], 0); } s.in(a[i]); int cur = f.get(1, 1, n, 1, a[i] - 1) + 1; f.up(1, 1, n, a[i], cur); ans = max(ans, cur); } cout << ans; } } signed main() { Keiiiii if(fopen("TASK.INP", "r")) { freopen("TASK.INP", "r", stdin); freopen("TASK.OUT", "w", stdout); } #define TASK "IMPAIR" if(fopen(TASK ".INP", "r")) { freopen(TASK ".INP", "r", stdin); freopen(TASK ".OUT", "w", stdout); } int TEST = 1; while(TEST--) { READ(); SOLVE(); } cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n"; return 0; } /// /\_/\ /// (= ._.) /// / > \>

Compilation message (stderr)

Main.cpp:176:1: warning: multi-line comment [-Wcomment]
  176 | ///    /\_/\
      | ^
Main.cpp: In function 'int main()':
Main.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen("TASK.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen("TASK.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         freopen(TASK ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen(TASK ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...