Submission #1246624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246624		bleahbleah	Distributing Candies (IOI21_candies)	C++20	0 / 100	5087 ms	22592 KiB

candies

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int qmax = 2e5 + 5;
const int nmax = 2e5 + 5;

namespace DS {
   int v[qmax];
   int Q;
   void upd(int p, int x) {
      v[p] += x;
   }
   
   int solve(int C) {
      int p = -1, mn = 0;
      int sum = 0;
      for(int i = 0; i < Q; i++) {
         sum += v[i];
         if(sum <= mn) mn = sum, p = i;
      }
      vector<int> a, bad, nxtbad;
      a.emplace_back(0);
      for(int i = p + 1; i < Q; i++) a.emplace_back(a.back() + v[i]);
      vector<int> mx;
      mx.emplace_back(0);
      for(auto x : a | views::reverse) mx.emplace_back(max(mx.back(), x));
      reverse(all(mx));
      
      bad.assign(sz(a), 0);
      nxtbad.assign(sz(a), 0);
      
      mn = a.back();
      for(int i = sz(a) - 1; i >= 0; i--) {
         mn = min(mn, a[i]);
         if(mn == a[i]) bad[i] = 1, nxtbad[i] = mn;
         else nxtbad[i] = nxtbad[i + 1];
      }
      int rez = a.back();
      for(int i = 0; i < sz(a); i++) {
         if(bad[i]) mn = a[i];
         if(mx[i] - mn >= C) rez = a.back() - min(mx[i] - C, nxtbad[i]);
         else break;
      }
      return max(rez, 0);
   }
   
}

vector<pii> opers[nmax];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
   DS::Q = sz(l);
   for(int i = 0; i < sz(l); i++) {
      opers[l[i]].emplace_back(i, v[i]);
      opers[r[i] + 1].emplace_back(i, -v[i]);
   }
   
   vector<int> rez;
   for(int i = 0; i < sz(c); i++) {
      for(auto [p, x] : opers[i]) DS::upd(p, x);
      rez.emplace_back(DS::solve(c[i]));
   }
   
   return rez;
}
                                    
/**

1) Din punctul de vedere al datului cu capu de podea, suma minima pe prefix este un punct bun de inceput
* 0 13 4 7 20 9 12 10
* fie caderea la:
* 0 13 4 7 13 2 5 3
* si daca primul 13 ar fi gatuit de 1 sau cv mic rau, daca scadem din el:
* 0 12 3 6 12 1 4 3
* 
* 
* sau daca il ignoram:
* 0 (13 4 7) 12 1 5 3
* 
* gatuirea ori e facuta la primul 13 iar apoi la al doilea ori direct la al doilea => chiar nu cont, de interes este deci urm maxim
* as fi tentat chiar sa spun ca:
* 
* tehnic vorbind gatuirile nu se intampla una dupa alta (i.e. ai geva ca in cazul asta 4 care nu ajunge niciodata in mod relevant la 0)
* 
* Dar daca o gatuire de 9 se face si avea una de 7 inainte, atunci putem spune ca efectul final (care e de macar -9 pe final) e subiectul unei telescopari de la gatuirea intai pana la 7, apoi ce a ramas din 9 dupa asta (-2 + -7 = -9)
* In fine
* sa zicem ca (cumva) nsh ce gatuire se intampla.
* 
* Ma gandesc ca singura conditie e ca nimic de dupa sa fie gen prea mare?
* si doar caut binar asa ceva?
* bine, ultima gatuire a.i. ceva de dupa e prea mare
* apoi scad diferenta 
* 
* de ce e asa de penal in retrospectiva??
* 
* 
      
--
*/ 

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33