oj.uz

Submission #503510

# Submission time Handle Problem Language Result Execution time Memory
503510 2022-01-08T08:38:57 Z AriaH Candies (JOI18_candies) C++17
100 / 100
 746 ms 38200 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 = 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))
    {
        /*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(l < 1 || r > n) continue;
        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))
        {
            ///printf("im here\n");
            pii cu = *Right.lower_bound(Mp(l - 1, -1));
            Del(cu.S, cu.F);
            l = cu.S;
        }
        else
        {
            l --;
        }
        if(get(r + 2))
        {
            ///printf("im not here\n");
            pii cu = *Left.lower_bound(Mp(r + 1, -1));
            Del(cu.F, cu.S);
            r = cu.S;
        }
        else
        {
            r ++;
        }
        ///printf("l = %d r = %d\n", l, 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);
            }
            st.insert(Mp(-Sum(l, r) + Sum(l + 1, r - 1), Mp(l, r)));
            Right.insert(Mp(r, l));
            Left.insert(Mp(l, r));
        }
        else
        {
            st.insert(Mp(inf, 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]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 3 ms 696 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 3 ms 696 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 3 ms 708 KB Output is correct
13 Correct 3 ms 696 KB Output is correct
14 Correct 3 ms 716 KB Output is correct
15 Correct 3 ms 700 KB Output is correct
16 Correct 3 ms 692 KB Output is correct
17 Correct 3 ms 636 KB Output is correct
18 Correct 3 ms 716 KB Output is correct
19 Correct 3 ms 708 KB Output is correct
20 Correct 3 ms 716 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 3 ms 696 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 3 ms 696 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 3 ms 708 KB Output is correct
13 Correct 3 ms 696 KB Output is correct
14 Correct 3 ms 716 KB Output is correct
15 Correct 3 ms 700 KB Output is correct
16 Correct 3 ms 692 KB Output is correct
17 Correct 3 ms 636 KB Output is correct
18 Correct 3 ms 716 KB Output is correct
19 Correct 3 ms 708 KB Output is correct
20 Correct 3 ms 716 KB Output is correct
21 Correct 746 ms 38048 KB Output is correct
22 Correct 737 ms 38008 KB Output is correct
23 Correct 706 ms 38064 KB Output is correct
24 Correct 354 ms 37968 KB Output is correct
25 Correct 345 ms 38000 KB Output is correct
26 Correct 358 ms 37972 KB Output is correct
27 Correct 388 ms 38120 KB Output is correct
28 Correct 388 ms 38096 KB Output is correct
29 Correct 390 ms 38084 KB Output is correct
30 Correct 417 ms 38140 KB Output is correct
31 Correct 407 ms 38016 KB Output is correct
32 Correct 404 ms 37956 KB Output is correct
33 Correct 513 ms 38016 KB Output is correct
34 Correct 516 ms 38104 KB Output is correct
35 Correct 520 ms 38052 KB Output is correct
36 Correct 739 ms 38140 KB Output is correct
37 Correct 746 ms 37720 KB Output is correct
38 Correct 719 ms 37700 KB Output is correct
39 Correct 344 ms 37712 KB Output is correct
40 Correct 347 ms 37720 KB Output is correct
41 Correct 352 ms 37796 KB Output is correct
42 Correct 381 ms 37660 KB Output is correct
43 Correct 385 ms 38200 KB Output is correct
44 Correct 385 ms 37624 KB Output is correct
45 Correct 401 ms 37700 KB Output is correct
46 Correct 411 ms 37792 KB Output is correct
47 Correct 400 ms 37704 KB Output is correct
48 Correct 528 ms 37640 KB Output is correct
49 Correct 514 ms 37768 KB Output is correct
50 Correct 518 ms 37688 KB Output is correct