Submission #1050770

#TimeUsernameProblemLanguageResultExecution timeMemory
1050770dozerCandies (JOI18_candies)C++14
0 / 100
7 ms10076 KiB
#include <bits/stdc++.h> using namespace std; #define sp " " //#define endl "\n" #define pb push_back #define pii pair<int, int> #define st first #define nd second #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define LL node * 2 #define RR node * 2 + 1 #define N 300005 #define ll long long #define int long long const int modulo = 1e9 + 7; const ll INF = 2e18 + 7; int a[N], pre[2][N]; int32_t main(){ fileio(); fastio(); int n; cin>>n; for (int i = 1; i <= n; i++){ cin>>a[i]; pre[0][i] = pre[0][i - 1], pre[1][i] = pre[1][i - 1]; pre[i % 2][i] += a[i]; } set<array<int, 3>> s; set<pii> ranges; int ans = 0; for (int i = 1; i <= n; i++) s.insert({a[i], i, 0}); auto add_range = [&](int l, int r){ ranges.insert({l, r}); if (l == 1) return; int prv = pre[r % 2][r] - pre[r % 2][l - 1]; int curr = pre[(r + 1) % 2][r + 1] - pre[(r + 1) % 2][l - 2]; if (r < n) s.insert({curr - prv, l, r}); if (l > 1){ s.erase({a[l - 1], l - 1, 0}); } if (r < n){ s.erase({a[r + 1], r + 1, 0}); } }; auto del_range = [&](int l, int r){ ranges.erase({l, r}); if (l == 1) return; int prv = pre[r % 2][r] - pre[r % 2][l - 1]; int curr = pre[(r + 1) % 2][r + 1] - pre[(r + 1) % 2][l - 2]; if (r < n) { s.erase({curr - prv, l, r}); } }; auto shift = [&](array<int, 3> x){ ans += x[0]; int l = x[1], r = x[2]; if (r == 0){ s.erase(x); r = l; } else{ del_range(l, r); l--, r++; } auto it = ranges.lower_bound({r, 0}); if (it != ranges.end() && it->st == r + 2){ pii tmp = *it; del_range(tmp.st, tmp.nd); r = tmp.nd; } it = ranges.lower_bound({r, 0}); if (it != ranges.begin()){ it--; if (it->nd == l - 2){ pii tmp = *it; del_range(tmp.st, tmp.nd); l = tmp.st; } } add_range(l, r); }; for (int j = 1; j <= (n + 1) / 2; j++){ assert(!s.empty()); array<int, 3> curr = *s.rbegin(); shift(curr); cout<<ans<<endl; } cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n"; }

Compilation message (stderr)

candies.cpp: In function 'int32_t main()':
candies.cpp:9:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:24:2: note: in expansion of macro 'fileio'
   24 |  fileio();
      |  ^~~~~~
candies.cpp:9:59: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
      |                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:24:2: note: in expansion of macro 'fileio'
   24 |  fileio();
      |  ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...