Submission #442230

#	Time	Username	Problem	Language	Result	Execution time	Memory
442230		cpp219	Candies (JOI18_candies)	C++14	100 / 100	632 ms	28916 KiB

candies

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 3;
const ll Log2 = 20;
const ll inf = 1e16 + 7;
typedef pair<ll,ll> LL;

ll n,a[N],val[N];

set<LL> s;
set<ll> num;


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin>>n; val[0] = val[n + 1] = -inf; num.insert(0); num.insert(n + 1);
    for (ll i = 1;i <= n;i++) cin>>a[i],s.insert({a[i],i}),val[i] = a[i],num.insert(i);
    ll cur = 0,p;
    for (ll i = 1;i <= (n + 1)/2;i++){
        LL t = *s.rbegin(); s.erase(prev(s.end()));
        cur += t.fs; ll now = t.sc; num.erase(now);
        auto it1 = num.lower_bound(now),it2 = num.upper_bound(now);
        ll p = now,q = now;
        if (it1 != num.begin()) p = *prev(it1);
        if (it2 != num.end()) q = *it2;
        s.erase({val[p],p}); s.erase({val[q],q});
        val[p] += val[q] - t.fs; num.erase(q); s.insert({val[p],p});
        cout<<cur<<"\n";
    }
}

Compilation message (stderr)

candies.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
candies.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
candies.cpp: In function 'int main()':
candies.cpp:31:16: warning: unused variable 'p' [-Wunused-variable]
   31 |     ll cur = 0,p;
      |                ^
candies.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92