Pagini recente » Borderou de evaluare (job #2553528) | Cod sursa (job #1692309)
#include <stdio.h>
#include <set>
using std::set;
#define aibSize 131072
#define Nadejde 100000
int N, M;
char sign[Nadejde + 2];
int aib[aibSize + 1];
set <int> sl;
set <int>::iterator it;
void init() {
int i;
for (i = 1; i <= N; i++) {
sign[i] = '0';
}
}
void add(int x, int val) {
if (x != 0) {
do {
aib[x] += val;
x += x & -x;
} while (x <= aibSize);
}
}
int bSearch(int val) {
int x = 0, interval = aibSize >> 1;
while (interval) {
if (aib[x + interval] < val) {
val -= aib[x += interval];
}
interval >>= 1;
}
return x + 1;
}
void push(int x, char c) {
sl.insert(x);
sign[x] = c;
}
void pop(int x) {
sl.erase(x);
sign[x] = '0';
}
int left(int x) {
it = sl.lower_bound(x);
if (it == sl.begin()) {
return 1;
} else {
it--;
return *it;
}
}
int right(int x) {
it = sl.upper_bound(x);
if (it == sl.end()) {
return N + 1;
} else {
return *it;
}
}
int main(void) {
int i, a, b, task, lo, hi;
FILE *f = fopen("hotel.in", "r");
freopen("hotel.out", "w", stdout);
fscanf(f, "%d %d", &N, &M);
init();
/* Raspunde la intrebari. */
for (i = 1; i <= M; i++) {
fscanf(f, "%d", &task);
if (task == 1) {
fscanf(f, "%d %d", &a, &b);
b += a - 1;
/* Trebuie sa fim fix sub "a". */
if (!sl.empty()) {
it = sl.upper_bound(a);
it--;
if (it == sl.begin()) {
lo = 1;
} else {
lo = *it;
}
it++;
if (it == sl.end()) {
hi = N + 1;
} else {
hi = *it;
}
} else {
lo = 1;
hi = N + 1;
}
add(hi - lo, -1);
add(a - lo, +1);
add(hi - b - 1, +1);
if (sign[a] == '-') {
pop(a);
} else {
push(a, '+');
}
if (sign[b + 1] == '+') {
pop(b + 1);
} else {
push(b + 1, '-');
}
} else if (task == 2) {
fscanf(f, "%d %d", &a, &b);
b += a - 1;
/* Stergem o secventa inclusa intr-un sir de "1". */
if (sign[a] != '+' && sign[b + 1] != '-') {
sign[a] = '-';
sign[b + 1] = '+';
add(b - a + 1, +1);
/* Stergem prefixul unui sir de "1". */
} else if (sign[a] == '+' && sign[b + 1] != '-') {
pop(a);
push(b + 1, '+');
lo = left(a);
add(a - lo, -1);
add(b - lo + 1, +1);
/* Stergem sufixul unui sir de "1". */
} else if (sign[a] != '+' && sign[b + 1] == '-') {
push(a, '-');
pop(b + 1);
hi = right(b + 1);
add(hi - b - 1, -1);
add(hi - a, +1);
/* Stergem un sir de "1". */
} else {
pop(a);
pop(b + 1);
lo = left(a);
hi = right(b + 1);
add(hi - b - 1, -1);
add(a - lo, -1);
add(hi - lo, +1);
}
} else {
fprintf(stdout, "%d\n", bSearch(aib[aibSize]));
}
}
fclose(f);
fclose(stdout);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}