Submission #172431

#	Time	Username	Problem	Language	Result	Execution time	Memory
172431		mhy908	Candies (JOI18_candies)	C++14	0 / 100	3 ms	632 KiB

candies

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
set<pair<LL, int> > pq;
set<pii> s;
int n;
LL arr[200010], sum[2][200010];
void relax(int num){
    auto it=s.lower_bound(mp(num, inf));
    set<pii>::iterator ithi, itlo;
    bool hifl=false, lofl=false;
    if(it==s.end())hifl=true;
    else ithi=it;
    it--;
    if(it==s.begin())lofl=true;
    else{
        it--;
        itlo=it;
        it++;
    }
    int st, fin;
    if(lofl)st=it->F;
    else{
        LL tsum=sum[itlo->S%2][itlo->S]-sum[itlo->S%2][itlo->F-1];
        if(pq.find(mp(tsum, itlo->F))!=pq.end())pq.erase(mp(tsum, itlo->F));
        else pq.erase(mp(-tsum, itlo->F));
        st=itlo->F;
    }
    if(hifl)fin=it->S;
    else{
        LL tsum=sum[ithi->S%2][ithi->S]-sum[ithi->S%2][ithi->F-1];
        if(pq.find(mp(tsum, ithi->F))!=pq.end())pq.erase(mp(tsum, ithi->F));
        else pq.erase(mp(-tsum, ithi->F));
        fin=ithi->S;
    }
    LL ttsum=sum[it->S%2][it->S]-sum[it->S%2][it->F-1];
    if(pq.find(mp(ttsum, it->F))!=pq.end())pq.erase(mp(ttsum, it->F));
    else pq.erase(mp(-ttsum, it->F));
    s.erase(it);
    if(!lofl)s.erase(itlo);
    if(!hifl)s.erase(ithi);
    ttsum=sum[1-fin%2][fin]-sum[1-fin%2][st-1];
    if((fin-num)%2)pq.insert(mp(-ttsum, st));
    else pq.insert(mp(ttsum, st));
    s.insert(mp(st, fin));
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        s.insert(mp(i, i));
        scanf("%lld", &arr[i]);
        pq.insert(mp(arr[i], i));
        sum[i%2][i]=sum[i%2][i-1]+arr[i];
        sum[1-i%2][i]=sum[1-i%2][i-1]-arr[i];
    }
    LL ans=0;
    for(int i=1; i<=(n+1)/2; i++){
        auto it=pq.end();
        it--;
        pii t=*it;
        ans+=t.F;
        printf("%lld\n", ans);
        relax(t.S);
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
candies.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~~~

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