Mai intai trebuie sa te autentifici.
Cod sursa(job #2247237)
Utilizator | Data | 28 septembrie 2018 09:18:45 | |
---|---|---|---|
Problema | Hotel | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.17 kb |
#include <fstream>
using namespace std;
ifstream fin ("hotel.in");
ofstream fout ("hotel.out");
#define MAX 100001
//0 - camera ocupata
//1 - camera libera
int N, Q;
int T[MAX * 4], lst[MAX * 4], ldr[MAX * 4];
void Update(int, int, int, int, int, int);
void Fix(int, int, int);
void ConstructGraph(int, int, int);
int main()
{
fin >> N >> Q;
ConstructGraph(1, 1, N);
for (int i = 1, cer, pos, l; i <= Q; i ++)
{
fin >> cer;
if (cer == 3)fout << T[1] << '\n';
else
{
fin >> pos >> l;
if (cer == 1)Update(1, 1, N, pos, pos + l - 1, 0); // sosire
else if (cer == 2)Update(1, 1, N, pos, pos + l - 1, 1); //plecare
}
}
return 0;
}
void ConstructGraph(int node, int a, int b)
{
T[node] = lst[node] = ldr[node] = b - a + 1;
if (a >= b)
return;
int md = (a + b) / 2;
ConstructGraph(2 * node, a, md);
ConstructGraph(2 * node + 1, md + 1, b);
}
void Update(int node, int a, int b, int l, int r, int val)
{
if (a > r || b < l)return;
if (l <= a && b <= r)
{
T[node] = lst[node] = ldr[node] = val * (b - a + 1);
Fix(node, a, b);
}
else
{
Fix(node, a, b);
int mijl = (a + b) / 2;
Update(2 * node, a, mijl, l, r, val);
Update(2 * node + 1, mijl + 1, b, l, r, val);
lst[node] = lst[2 * node];
ldr[node] = ldr[2 * node + 1];
if (lst[node] == mijl - a + 1)
lst[node] += lst[2 * node + 1];
if (ldr[node] == b - mijl)
ldr[node] += ldr[2 * node];
T[node] = max(lst[2 * node], ldr[2 * node + 1]);
T[node] = max(T[node], ldr[2 * node] + lst[2 * node + 1]);
}
}
void Fix(int i, int a, int b)
{
if (T[i] == 0)
{
T[2 * i] = lst[2 * i] = ldr[2 * i] = 0;
T[2 * i + 1] = lst[2 * i + 1] = ldr[2 * i + 1] = 0;
}
else if (T[i] == b - a + 1)
{
int mijl = (a + b) / 2;
T[2 * i] = lst[2 * i] = ldr[2 * i] = mijl - a + 1;
T[2 * i + 1] = lst[2 * i + 1] = ldr[2 * i + 1] = b - mijl;
}
}