| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 503500 |
2022-01-08T08:18:55 Z |
AriaH |
Candies (JOI18_candies) |
C++14 |
|
3 ms |
576 KB |
/** 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 = 2e3 + 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))
{
/*for(int i = 1; i <= n; i ++)
{
printf("%d ", get(i));
}
printf("\n");
for(auto x : Left)
{
printf("%d %d\n", x.F, x.S);
}
printf("\n");
*/
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));
///printf("now : %d %d %lld\n", l, r, -Cu.F);
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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
