Monday, September 16, 2024

# Codeforces Round #408 (Div. 2), problem: (F) Sequence Recovery Solution in C/C++

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5, inf = 1e9 + 7;

int ma[N << 2], lz[N << 2], ma2[N << 2], n;
int vma[N];

void build1(int id = 1, int l = 0, int r = n) {
ma[id] = inf;
lz[id] = inf;
if (r-l < 2)
return;
int mid = (l+r) >> 1, il = id << 1, ir = il | 1;
build1(il, l, mid);
build1(ir, mid, r);
}
void shift(int id) {
if (lz[id] < inf) {
int il = id << 1, ir = il | 1;
ma[il] = min(ma[il], lz[id]);
lz[il] = min(lz[il], lz[id]);
ma[ir] = min(ma[ir], lz[id]);
lz[ir] = min(lz[ir], lz[id]);
lz[id] = inf;
}
}
int get1(int x, int id = 1, int l = 0, int r = n) {
if (r-l < 2)
return ma[id];
shift(id);
int mid = (l+r) >> 1, il = id << 1, ir = il | 1;
if (x < mid)
return get1(x, il, l, mid);
else
return get1(x, ir, mid, r);
}
void upd1(int x, int y, int val, int id = 1, int l = 0, int r = n) {
if (x >= r || l >= y) return;
if (x <= l && r <= y) {
ma[id] = min(ma[id], val);
lz[id] = min(lz[id], val);
return;
}
shift(id);
int mid = (l+r) >> 1, il = id << 1, ir = il | 1;
upd1(x, y, val, il, l, mid);
upd1(x, y, val, ir, mid, r);
ma[id] = max(ma[il], ma[ir]);
}

void build2(int id = 1, int l = 0, int r = n) {
if (r-l < 2) {
ma2[id] = vma[l];
return;
}
int mid = (l+r) >> 1, il = id << 1, ir = il | 1;
build2(il, l, mid);
build2(ir, mid, r);
ma2[id] = max(ma2[il], ma2[ir]);
}
int get2(int x, int y, int id = 1, int l = 0, int r = n) {
if (x >= r || l >= y) return -inf;
if (x <= l && r <= y) return ma2[id];
int mid = (l+r) >> 1, il = id << 1, ir = il | 1;
return max(get2(x, y, il, l, mid), get2(x, y, ir, mid, r));
}
void upd2(int x, int val, int id = 1, int l = 0, int r = n) {
if (r-l < 2) {
ma2[id] = val;
return;
}
int mid = (l+r) >> 1, il = id << 1, ir = il | 1;
if (x < mid)
upd2(x, val, il, l, mid);
else
upd2(x, val, ir, mid, r);
ma2[id] = max(ma2[il], ma2[ir]);
}
int t[N], x[N], y[N], z[N];

int main() {
int m;
scanf(“%d %d”, &n, &m);
fill(vma, vma+n, -1);
build1();
for (int i = 0; i < m; i++) {
scanf(“%d %d %d”, t+i, x+i, y+i);
x[i]–;
if (t[i] == 1) {
scanf(“%d”, z+i);
upd1(x[i], y[i], z[i]);
}
else {
if (vma[x[i]] == -1) {
vma[x[i]] = get1(x[i]);
}
}
}
for (int i = 0; i < n; i++) {
if (vma[i] == -1) vma[i] = get1(i);
}
build2();
bool ok = 1;
for (int i = 0; i < m; i++) {
if (t[i] == 1) {
int res = get2(x[i], y[i]);
if (res != z[i]) {
ok = 0;
break;
}
}
else
upd2(x[i], y[i]);
}
if (!ok) {
puts(“NO”);
return 0;
}
puts(“YES”);
map< int, int > mp;
for (int i = 0; i < n; i++) {
mp[vma[i]]++;
}
if (mp[inf] > 1) {
for (int i = 0; i < n; i++) {
if (vma[i] == inf) {
if (–mp[inf] == 0)
vma[i] = (1<<29)-1;
else
vma[i] = 1e9;
}
}
}
else {
int all = 0;
for (int i = 0; i < n; i++) {
if (vma[i] == inf || vma[i] == 0) continue;
if (mp[vma[i]] > 1) {
int lg = 31-__builtin_clz(vma[i]);
mp[vma[i]]–;
vma[i] = (1<<lg)-1;
}
all |= vma[i];
}
int now = 0;
for (int i = 29; i >= 0; i–) {
if (all & (1<<i)) continue;
if (now + (1<<i) > 1e9) continue;
now |= 1<<i;
}
for (int i = 0; i < n; i++)
if (vma[i] == inf)
vma[i] = now;
}
for (int i = 0; i < n; i++) {
if (i) printf(” “);
printf(“%d”, vma[i]);
}
printf(“\n”);
return 0;
}

## 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...