Pagini recente » Autentificare | Cod sursa (job #202336) | Cod sursa (job #2020191) | Istoria paginii utilizator/meandyou01 | Cod sursa (job #2016098)
#include <stdio.h>
#include <math.h>
typedef struct {
int max;
int stg;
int dr;
int de_updatat;
} batog;
int n, m;
int sqrt_n;
int v[100000];
batog w[4000];
void update_interval (int nr) {
int stg = 0, dr = 0, max = 0;
int i;
for (i = (nr - 1) * sqrt_n + 1; i <= nr * sqrt_n; i++)
if (v[i] == 1)
stg++;
else
break;
for (i = nr * sqrt_n; i >= (nr - 1) * sqrt_n + 1; i--)
if (v[i] == 1)
dr++;
else
break;
int max_p = 0;
for (i = (nr - 1) * sqrt_n + 1; i <= nr * sqrt_n; i++)
if (v[i] == 1)
max_p++;
else {
if (max < max_p) max = max_p;
max_p = 0;
}
if (max < max_p) max = max_p;
w[nr].stg = stg;
w[nr].dr = dr;
w[nr].max = max;
w[nr].de_updatat = 0;
}
void de_update_intervale (int nr) {
int i;
for (i = (nr - 1) * sqrt_n + 1; i <= nr * sqrt_n; i++)
v[i] = w[nr].max;
}
void update (int left, int right, int value) {
int first_interval = left / sqrt_n + 1; if (left % sqrt_n == 0) first_interval--;
int last_interval = right / sqrt_n + 1; if (right % sqrt_n == 0) last_interval--;
if (w[first_interval].de_updatat == 1) {
de_update_intervale (first_interval);
update_interval (first_interval);
}
if (w[last_interval].de_updatat == 1) {
de_update_intervale (last_interval);
update_interval (last_interval);
}
int i;
// daca e acelasi interval, terminam repede
if (first_interval == last_interval) {
for (i = left; i <= right; ++i)
v[i] = value;
update_interval (first_interval);
return;
}
// mergem pana la primul interval
for (i = left; i < first_interval * sqrt_n + 1; i++)
v[i] = value;
// mergem din interval in interval pana la ultimul - 1;
for (i = first_interval + 1; i <= last_interval - 1; i++) {
if (value == 1) {
w[i].max = sqrt_n;
w[i].stg = sqrt_n;
w[i].dr = sqrt_n;
w[i].de_updatat = 1;
} else {
w[i].max = 0;
w[i].stg = 0;
w[i].dr = 0;
w[i].de_updatat = 1;
}
}
// mergem de la ultimul - 1, pana unde trebuie
for (i = (last_interval - 1) * sqrt_n + 1; i <= right; i++)
v[i] = value;
// updatam intervalele din capete
update_interval (first_interval);
update_interval (last_interval);
}
int query () {
int max = w[1].max;
int max_p = w[1].dr;
int i;
for (i = 2; i <= n / sqrt_n + 1; i++){
if (max < w[i].max)
max = w[i].max;
if (w[i].max == sqrt_n)
max_p += sqrt_n;
else
max_p += w[i].stg;
if (max < max_p)
max = max_p;
if (w[i].max != sqrt_n)
max_p = w[i].dr;
}
return max;
}
int main(){
freopen ("hotel.in", "r", stdin);
// freopen ("hotel.out", "w", stdout);
scanf ("%d %d\n", &n, &m);
sqrt_n = sqrt(n);
int i;
for (i = 1; i <= n; ++i) {
v[i] = 1;
if (i <= sqrt_n + 1) {
w[i].max = sqrt_n;
w[i].stg = sqrt_n;
w[i].dr = sqrt_n;
w[i].de_updatat = 0;
}
}
for (i = 0; i < m; ++i) {
int op;
scanf ("%d", &op);
if (op == 1) {
int left, right, add;
scanf ("%d %d", &left, &add);
right = left + add - 1;
//printf ("update %d %d 0\n", left, right);
update (left, right, 0);
} else if (op == 2) {
int left, right, add;
scanf ("%d %d", &left, &add);
right = left + add - 1;
//printf ("update %d %d 1\n", left, right);
update (left, right, 1);
} else if (op == 3) {
printf ("%d\n", query());
}
/*
int j;
for (j = 1; j <= n; ++j)
printf ("%d ", v[j]);
printf ("\n");
for (j = 1; j <= n / sqrt_n + 1; ++j)
printf ("%d => %d %d %d %d\n", j, w[j].stg, w[j].dr, w[j].max, w[j].de_updatat);
printf ("\n");
*/
}
return 0;
}