Expert.
Put your skills to the test.

Problem summary

Each activation at (x,y) permanently lights all cells within Manhattan distance K, clipped to an N×M floor. Report the number of lit cells after every activation.

Source clarification. The PDF header prints 7 January 2023 although Arena assigns the 2024 season. The code also supports the K=0 cases explicitly listed among tests.

Constraints

1 ≤ N,M ≤ 500; 1 ≤ K ≤ 500 in the main bounds, with K=0 explicitly included in tests; 1 ≤ Q ≤ 300000.

Worked example

Official statement example.

7 8 2 5
2 2
4 3
1 8
5 6
2 2

11
20
26
37
37

Solution analysis

1. Intersect the diamond with a row r. If |r−x|≤K, the illuminated columns form the interval [y−(K−|r−x|), y+(K−|r−x|)], clipped to the floor. Thus one command is at most N interval insertions.
2. For each row, a successor DSU stores the first still-unlit cell at or after a column. Once a cell lights, remove it by linking it to its successor. Repeatedly finding the successor from the interval start visits only previously unlit cells. A second successor DSU skips completely lit rows.
3. The total number of cell removals is at most NM over all commands, even if diamonds overlap heavily. In the example the fifth command repeats the first, so successor searches discover no new cells and the answer remains 37.

Why it works

Each row interval is precisely the set of cells in that row at Manhattan distance at most K. Successor links skip exactly cells already lit and remove each newly lit cell once. Therefore processing these intervals adds precisely the newly lit cells of a diamond; skipping an entirely lit row cannot alter the union. The maintained count is the required cumulative union size.

Watch out. Clip both row and column bounds. Lighting does not toggle cells, and activating an already lit center can still light other cells.

An independently written complete program with standard headers.

// Key idea: Each row interval is precisely the set of cells in that row at Manhattan distance at most
// K. Successor links skip exactly cells already lit and remove each newly lit cell once.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int findRoot(vector<int>&parent,int x){
    int root=x;
    while(parent[root]!=root){
        root=parent[root];
    }
    while(parent[x]!=x){
        int next=parent[x];
        parent[x]=root;
        x=next;
    }
    return root;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k,q;
    cin>>n>>m>>k>>q;
    int stride=m+1;
    vector<int>parent(n*stride),rows(n+1);
    iota(parent.begin(),parent.end(),0);
    iota(rows.begin(),rows.end(),0);
    int total=0;
    while(q--){
        int x,y;
        cin>>x>>y;
        --x;
        --y;
        int endRow=min(n-1,x+k);
        for(int r=findRoot(rows,max(0,x-k));r<=endRow;r=findRoot(rows,r+1)){
            int radius=k-abs(r-x);
            int left=max(0,y-radius);
            int right=min(m-1,y+radius);
            int base=r*stride;
            int cell=findRoot(parent,base+left);
            while(cell<=base+right){
                ++total;
                parent[cell]=findRoot(parent,cell+1);
                cell=parent[cell];
            }
            if(findRoot(parent,base)==base+m){
                rows[r]=findRoot(rows,r+1);
            }
        }
        cout<<total<<'\n';
    }
}