Submission #61705

#	Time	Username	Problem	Language	Result	Execution time	Memory
61705		mAng0	Candies (JOI18_candies)	C++17	0 / 100	5 ms	504 KiB

candies

#include<bits/stdc++.h>
using namespace std;

using interval = pair<int, int>;
#define s first
#define e second

map<interval, long long> mp;

using qtype = pair<long long, interval>;
priority_queue<qtype> pq;

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        long long x;
        scanf("%lld",&x);
        mp[{i, i}] = x;
        pq.push({x, {i, i}});
    }
    long long ans = 0;
    for(int i=0;i<(n+1)/2;i++){
        while(true){
            auto it = mp.find(pq.top().second);
            if(it == mp.end()){
                pq.pop();
            }else{
                if((*it).second == pq.top().first){
                    break;
                }else{
                    pq.pop();
                }
            }
        }
        //printf("hi: %d - %d, %lld\n", pq.top().second.s, pq.top().second.e, pq.top().first);
        qtype top = pq.top();
        ans += top.first;
        interval tt = top.second;
        pq.pop();
        interval newtt = top.second;
        long long newval = -top.first;
        long long vall = top.first;
        auto pit = mp.find(tt);
        auto nit = pit; nit++;
        if(pit != mp.begin()){
            pit--;
            newtt.s = (*pit).first.s;
            newval += (*pit).second;
            //printf("del: %d - %d, %lld\n", (*pit).first.s, (*pit).first.e, (*pit).second);
            mp.erase(pit);
        }
        if(nit != mp.end()){
            newtt.e = (*nit).first.e;
            newval += (*nit).second;
            //printf("del: %d - %d, %lld\n", (*nit).first.s, (*nit).first.e, (*nit).second);
            mp.erase(nit);
        }
        //printf("del: %d - %d, %lld\n", tt.s, tt.e, vall);
        mp.erase(tt);
        mp[newtt] = newval;
        //printf("add: %d - %d, %lld\n", newtt.s, newtt.e, newval);
        pq.push({newval, newtt});
        printf("%lld\n", ans);
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:43:19: warning: unused variable 'vall' [-Wunused-variable]
         long long vall = top.first;
                   ^~~~
candies.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
candies.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&x);
         ~~~~~^~~~~~~~~~~

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