Submission #503501

#TimeUsernameProblemLanguageResultExecution timeMemory
503501AriaHCandies (JOI18_candies)C++17
0 / 100
4 ms716 KiB
/** I can do this all day **/ #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair < int, int > pii; typedef pair < ll, ll > pll; #define F first #define S second #define all(x) x.begin(), x.end() #define SZ(x) (int)x.size() #define Mp make_pair #define endl "\n" #define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define file_io freopen("inupt.txt", "r+", stdin); freopen("output.txt", "w+", stdout); const int N = 1e6 + 10; const ll mod = 1e9 + 7; const ll inf = 1e18; const int LOG = 20; ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; } ll ps[N], Ans[N]; int n, ptr, A[N], fen[N]; void add(int i) { for(i += 5; i < N; i += i & -i) { fen[i] ^= 1; } } void add(int l, int r) { add(l); add(r + 1); } int get(int i, int ret = 0) { for(i += 5; i; i -= i & -i) ret ^= fen[i]; return ret; } inline ll Sum(int l, int r) { if(l > r) return 0ll; if(r < 0) return 0ll; return ps[r] - (l > 1? ps[l - 2] : 0); } set < pair < ll, pii > > st; set < pii > Left, Right; void Del(int l, int r) { Left.erase(Mp(l, r)); Right.erase(Mp(r, l)); st.erase(Mp(-Sum(l, r) + Sum(l + 1, r - 1), Mp(l, r))); } int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++) { scanf("%d", &A[i]); ps[i] = A[i] + (i > 1? ps[i - 2] : 0); } ps[n + 1] = ps[n - 1]; ps[n + 2] = ps[n]; for(int i = 1; i <= n; i ++) { st.insert(Mp(-A[i], Mp(i, i))); Left.insert(Mp(i, i)); Right.insert(Mp(i, i)); } ptr = 0; while(SZ(st)) { pair < ll, pii > Cu = *st.begin(); st.erase(st.begin()); int l = Cu.S.F, r = Cu.S.S; Left.erase(Mp(l, r)); Right.erase(Mp(r, l)); if(get(l - 1) == 1 || get(r + 1) == 1) continue; ptr ++; Ans[ptr] = Ans[ptr - 1] + (-Cu.F); add(l, r); if(get(l - 2)) { pii cu = *Right.lower_bound(Mp(l - 1, -1)); Del(cu.S, cu.F); l = cu.S; } else { l --; } if(get(r + 2)) { pii cu = *Left.lower_bound(Mp(r + 1, -1)); ///printf("im here cu = %d %d\n", cu.F, cu.S); Del(cu.F, cu.S); r = cu.S; } else { r ++; } if(l >= 1 && r <= n) { if(Left.find(Mp(l, l)) != Left.end()) { Del(l, l); } if(Right.find(Mp(r, r)) != Right.end()) { Del(r, r); } ///printf("adding %d %d\n", l, r); st.insert(Mp(-Sum(l, r) + Sum(l + 1, r - 1), Mp(l, r))); Right.insert(Mp(r, l)); Left.insert(Mp(l, r)); } } for(int i = 1; i <= (n + 1) >> 1; i ++) { printf("%lld\n", Ans[i]); } return 0; } /** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
candies.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...