Monday, August 5, 2024

# Codeforces Round #426 (Div. 1), problem: (E) Caramel Clouds Solution In C/C++

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <utility>
#include <vector>

const int N = 300000;

struct Sum
{
{
if (a[0].second == id) {
a[0].first = std::max(a[0].first, value);
} else if (a[1].first < value) {
a[1] = {value, id};
}
if (a[0].first < a[1].first) {
std::swap(a[0], a[1]);
}
}

{
if (a[0].second != id) {
return a[0].first;
}
return a[1].first;
}

std::pair<int, int> a[2] = {{0, -1}, {0, -1}};
};

int cost[N + 1], toupd[N];

int main()
{
#ifdef LOCAL_JUDGE
freopen(“E.in”, “r”, stdin);
#endif
int n, budget;
while (scanf(“%d%d”, &n, &budget) == 2) {
cost[n] = 0;
std::vector<std::pair<int, int>> events;
events.emplace_back(0, n);
events.emplace_back(2000000000, n);
for (int i = 0, l, r; i < n; ++ i) {
scanf(“%d%d%d”, &l, &r, cost + i);
events.emplace_back(l, i);
events.emplace_back(r, i);
}
std::sort(events.begin(), events.end());
std::vector<int> values(cost, cost + n);
std::sort(values.begin(), values.end());
values.erase(std::unique(values.begin(), values.end()), values.end());
std::set<int> covers;
if (events[0].second < n) {
covers.insert(events[0].second);
}
int curmx = 0;
std::vector<std::pair<int, int>> parts;
memset(toupd, 0, sizeof(toupd));
std::vector<Sum> bit(values.size());
std::map<std::pair<int, int>, int> length;
for (int t = 1; t < (int)events.size(); ++ t) {
int mxlen = events[t].first – events[t – 1].first;
if (mxlen > 0 && (int)covers.size() <= 2) {
int p = n, q = n;
if ((int)covers.size() > 0) {
p = *covers.begin();
}
if ((int)covers.size() > 1) {
q = *covers.rbegin();
}
int start = -1;
if (p == n) { // 0
start = curmx;
} else {
if (q == n) { // 1
if (cost[p] <= budget) {
start = toupd[p];
for (int k = (int)(std::upper_bound(values.begin(), values.end(), budget – cost[p]) – values.begin()) – 1; k >= 0; k -= ~k & k + 1) {
}
auto value = length[{p, q}] + mxlen;
for (int k = std::lower_bound(values.begin(), values.end(), cost[p]) – values.begin(); k < (int)values.size(); k += ~k & k + 1) {
}
}
} else if (cost[p] + cost[q] <= budget) {
start = length[{p, n}] + length[{q, n}];
toupd[p] = std::max(toupd[p], length[{q, n}] + length[{p, q}] + mxlen);
toupd[q] = std::max(toupd[q], length[{p, n}] + length[{p, q}] + mxlen);
}
if (~start) {
start += length[{p, q}] + length[{n, n}];
}
}
if (~start && start + mxlen > curmx) {
curmx = start + mxlen;
parts.emplace_back(curmx, events[t].first);
}
length[{p, q}] += mxlen;
}
auto&& i = events[t].second;
if (i < n) {
if (covers.count(i)) {
covers.erase(i);
} else {
covers.insert(i);
}
}
}
int q, t;
scanf(“%d”, &q);
while (q –) {
scanf(“%d”, &t);
auto it = std::lower_bound(parts.begin(), parts.end(), std::make_pair(t, 0));
printf(“%d\n”, it->second – (it->first – t));
}
}
}

## Celebrating Black History Month:...

As February unfolds, so does the annual celebration of...

## The Path to Self-Mastery:...

Embarking on a journey of self-mastery and breaking free...

## Wizards of Waverly Place...

In a spellbinding announcement, Disney has officially revealed that...

## Jim Irsay’s Reported ‘Suspected...

In a shocking turn of events last month, Jim...

Coachella Valley Music and Arts Festival, one of the...

## 2024 Taiwan Election: Pivotal...

As Taiwan gears up for its 2024 presidential election,...

### Celebrating Black History Month: Past, Future

As February unfolds, so does the annual celebration of Black History Month, a time to reflect on the profound contributions, resilience, and rich cultural...

### The Path to Self-Mastery: Lessons from Book ‘The Mountain Is You’

Embarking on a journey of self-mastery and breaking free from self-sabotage is a transformative process that requires dedication and conscious effort. Brianna Wiest's insightful...

### Wizards of Waverly Place Cast Reunites for Enchanting Revival

In a spellbinding announcement, Disney has officially revealed that the beloved fantasy series "Wizards of Waverly Place" is set for a magical comeback, featuring...

### Jim Irsay’s Reported ‘Suspected Overdose’: A Closer Look

In a shocking turn of events last month, Jim Irsay, the owner of the Indianapolis Colts, was reportedly found unresponsive at his home in...

### Coachella 2024: Iconic headliners, unforgettable musical experience!

Coachella Valley Music and Arts Festival, one of the most iconic and eagerly anticipated music festivals globally, has just dropped its highly anticipated lineup...

### 2024 Taiwan Election: Pivotal Moment in Political Landscape

As Taiwan gears up for its 2024 presidential election, the political landscape is buzzing with anticipation and fervor. With the island nation situated at...

### Michael Strahan’s Daughter’s Medulloblastoma Diagnosis

In a recent and heartbreaking revelation, Michael Strahan, former NFL star and television personality, shared the devastating news of his daughter Isabella's diagnosis with...

### Michigan vs. Washington: The 2024 National Championship Clash

In a highly anticipated matchup, the 2024 National Championship will witness a clash of football titans as the Michigan Wolverines square off against the...

### Jason Kelce: Unmasking the Unconventional NFL Icon

In the world of professional football, where conformity often takes center stage, one player stands out as a beacon of individuality, both on and...