제출 #1246617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246617		bleahbleah	사탕 분배 (IOI21_candies)	C++17	컴파일 에러	0 ms	0 KiB

candies

// evident ca refacem, ar fi o minune sa ma duca capu ca pe vremuri
#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;
      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);
      
      mn = a.back();
      for(int i = sz(a) - 1; i >= 0; i--) {
         mn = min(mn, a[i]);
         if(mn == a[i]) bad[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() - mx[i] + C;
         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??
* 
* 
      
--
*/ 

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'int DS::solve(int)':
candies.cpp:37:24: error: 'views' has not been declared
   37 |       for(auto x : a | views::reverse) mx.emplace_back(max(mx.back(), x));
      |                        ^~~~~