Submission #1209082

#TimeUsernameProblemLanguageResultExecution timeMemory
1209082matthewBouquet (EGOI24_bouquet)C++20
100 / 100
77 ms14548 KiB
#include <stdio.h> #include <algorithm> #include <vector> const int MAX_N = 2e5; struct AIB { int n; int aib[MAX_N + 1]; void init(int _n) { n = _n; } int query_max(int pref) { int res = 0; for(; pref > 0; pref &= pref - 1) { res = std::max(res, aib[pref]); } return res; } void update(int pos, int val) { for(; pos <= n; pos += pos & -pos) { aib[pos] = std::max(aib[pos], val); } } }; int l[MAX_N], r[MAX_N]; AIB aib; std::vector<int> updates[MAX_N + 1]; int dp[MAX_N]; void clamp_max(int &val, int max) { if(val > max) { val = max; } } int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d%d", &l[i], &r[i]); clamp_max(l[i], i); clamp_max(r[i], n - 1 - i); } aib.init(n); int res = 0; for(int i = 0; i < n; i++) { for(int x : updates[i]) { aib.update(x + 1, dp[x]); } int leftb = i + 1 - l[i]; dp[i] = 1 + aib.query_max(leftb - 1); if(dp[i] > res) { res = dp[i]; } updates[i + r[i] + 1].push_back(i); } printf("%d\n", res); return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
Main.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d%d", &l[i], &r[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...