Submission #44349

#	Time	Username	Problem	Language	Result	Execution time	Memory
44349		ruhanhabib39	Candies (JOI18_candies)	C++17	100 / 100	902 ms	28124 KiB

candies

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

const int MAXN = 2e5;
const long long INF = 1e16;

typedef set<pair<long long,long long>,greater<pair<long long,long long>>> inc_set;

long long N;
inc_set pos, val;
long long res[MAXN + 10];

int main() {
   scanf("%lld", &N);
   for(long long i = 0; i < N; i++) {
      long long a; scanf("%lld", &a);
      pos.emplace(i, a);
      val.emplace(a, i);
   }
   pos.emplace(-1LL, -INF); pos.emplace(N, -INF);
   val.emplace(-INF, -1LL); val.emplace(-INF, N);
   long long ss = 0;
   for(int i = 0; i < (N+1)/2; i++) {
      auto valIt = val.begin();

      ss += valIt->first;
      res[i] = ss;

      auto posIt = pos.find({valIt->second, valIt->first});
      auto x = *prev(posIt);
      auto y = *posIt;
      auto z = *next(posIt);

      for(auto it : {x,y,z}) {
         pos.erase(it);
         val.erase({it.second, it.first});
      }

      pos.insert({y.first, x.second + z.second - y.second});
      val.insert({x.second + z.second - y.second, y.first});
   }

   for(int i = 0; i < (N + 1)/2; i++) {
      printf("%lld\n", res[i]);
   }

}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:14:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &N);
    ~~~~~^~~~~~~~~~~~
candies.cpp:16:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       long long a; scanf("%lld", &a);
                    ~~~~~^~~~~~~~~~~~

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