oj.uz

Submission #95827

# Submission time Handle Problem Language Result Execution time Memory
95827 2019-02-02T19:03:21 Z Kastanda Candies (JOI18_candies) C++11
0 / 100
 3 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n, L[N], R[N];
ll A[N];
set < pair < ll , int > > S;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &A[i]);
        L[i] = i - 1; R[i] = i + 1;
        S.insert({A[i], i});
    }
    ll Mx = 0;
    for (int i = 0; i < (n + 1 >> 1); i++)
    {
        int id = S.rbegin()->second;
        S.erase(*S.rbegin());
        Mx += A[id];
        printf("%lld\n", Mx);
        int le = L[id], ri = R[id];
        if (le <= 0 || ri > n)
        {
            S.erase({A[le], le});
            S.erase({A[ri], ri});
            L[R[ri]] = 0;
            R[L[le]] = 0;
            continue;
        }
        ll tobe = 0;
        L[id] = L[le];
        S.erase({A[le], le});
        tobe += A[le];
        R[id] = R[ri];
        S.erase({A[ri], ri});
        tobe += A[ri];
        tobe -= A[id];
        L[R[id]] = id;
        R[L[id]] = id;
        A[id] = tobe;
        S.insert({A[id], id});
    }
    return 0;
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:18:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     for (int i = 0; i < (n + 1 >> 1); i++)
                          ~~^~~
candies.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
candies.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &A[i]);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Incorrect 3 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Incorrect 3 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -