palavraSeg.cpp

// Parciais 1-6: 84 pontos

#include <bits/stdc++.h>
using namespace std;

const int MAXN = (1 << 21) + 10;
array<int, 2*MAXN+1> seg, peso;

void refresh(int pos, int nivel) // Atualiza o no pos
{
    if (nivel == 21) {seg[pos] = peso[pos]; return;}
    int e = 2*pos, d = e+1;
    seg[pos] = peso[pos] + min(seg[e], seg[d]);
}

void update(int pos, int nivel, int x, int id, int val) //pos na seg, nivel na arvore, nivel que quero chegar, id na seq, val pra atualizar
{
    if (nivel == x) return;
    vector<int> viz = {2*pos, 2*pos + 1};
    int chosenViz = 0;
    if (nivel+1 == x) chosenViz = (id&1);
    else chosenViz = !(id&1);
    peso[viz[!chosenViz]] += val;
    update(viz[chosenViz], nivel+1, x, id>>1, val);
    refresh(viz[!chosenViz], nivel+1);
    refresh(pos, nivel);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q, K;
    cin >> N >> Q >> K;
    
    vector<int> seq(N);
    for (auto &x : seq) cin >> x;
    seq.insert(seq.begin(), 0);

    for (int i = 1; i <= N; i++)
    {
        if (seq[i] > 21) seq[i] = 21;
        update(1, 0, seq[i], i, +1);
    }

    cout << (seg[1] <= K ? 1 : 0) << '\n';
    
    while (Q--)
    {
        int i, X;
        cin >> i >> X;
        update(1, 0, seq[i], i, -1);
        seq[i] = min(X, 21);
        update(1, 0, seq[i], i, +1);
        
        cout << (seg[1] <= K ? 1 : 0) << '\n';
    }
}