Proficient.
Put your skills to the test.

Problem summary

Robots start on cells of an M×N table and move straight left, right, up or down until falling off. Every visited cell, including its start, becomes dirty. Count the distinct dirty cells.

Constraints

0≤K≤15000; 1≤M,N≤30000; several robots may share a starting cell.

Worked example

An independently prepared example for this explanation.

8 5 4
1 2 r
1 3 d
2 3 r
2 3 l
2 4 d
3 2 l
4 1 u
4 4 u

17

Solution analysis

1. Each horizontal trail is an inclusive interval in one row, and each vertical trail an interval in one column. Merge overlapping or adjacent intervals separately in every row and every column. Sum their lengths to obtain horizontal coverage H and vertical coverage V.
2. Now subtract cells covered in both directions. Sweep columns. A merged horizontal interval activates its row at its left endpoint and deactivates it one column after its right endpoint. A Fenwick tree of active rows answers how many horizontal trails cross each vertical interval in the current column.
3. The sample has overlapping robot starts and trails, so adding individual travel lengths would double-count. After merging same-direction coverage and subtracting horizontal–vertical intersections, the union contains 17 cells. K=0 naturally produces zero.

Why it works

Merging preserves each orientation’s covered set and makes its intervals disjoint. During the sweep a row is active exactly when its cell in the current column is horizontally covered. Each query therefore counts exactly the intersection cells for one disjoint vertical interval. Inclusion–exclusion H+V−intersection gives the union size.

Watch out. Include the starting cell. Use inclusive lengths r−l+1 and remove a row at r+1. Merge before intersection counting so an overlap is subtracted exactly once.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
vector<pair<int,int>>mergeIntervals(vector<pair<int,int>>intervals){
    sort(intervals.begin(),intervals.end());
    vector<pair<int,int>>merged;
    for(auto interval:intervals){
        if(merged.empty()||interval.first>merged.back().second+1){
            merged.push_back(interval);
        }
        else{
            merged.back().second=max(merged.back().second,interval.second);
        }
    }
    return merged;
}
struct Fenwick{
    vector<int>tree;
    explicit Fenwick(int size):tree(size+1,0){
    }
    void add(int index,int delta){
        for(;index<static_cast<int>(tree.size());index+=index&-index){
            tree[index]+=delta;
        }
    }
    int prefix(int index)const{
        int result=0;
        for(;index>0;index-=index&-index){
            result+=tree[index];
        }
        return result;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int robots,rows,columns;
    cin>>robots>>rows>>columns;
    vector<vector<pair<int,int>>>horizontal(rows+1),vertical(columns+1);
    for(int i=0;i<robots;i++){
        int row,column;
        char direction;
        cin>>row>>column>>direction;
        if(direction=='l'){
            horizontal[row].push_back({1,column});
        }
        else if(direction=='r'){
            horizontal[row].push_back({column,columns});
        }
        else if(direction=='u'){
            vertical[column].push_back({1,row});
        }
        else{
            vertical[column].push_back({row,rows});
        }
    }
    vector<vector<pair<int,int>>>events(columns+2);
    long long answer=0;
    for(int row=1;row<=rows;row++){
        for(auto interval:mergeIntervals(horizontal[row])){
            answer+=interval.second-interval.first+1;
            events[interval.first].push_back({row,1});
            events[interval.second+1].push_back({row,-1});
        }
    }
    Fenwick active(rows);
    for(int column=1;column<=columns;column++){
        for(auto event:events[column]){
            active.add(event.first,event.second);
        }
        for(auto interval:mergeIntervals(vertical[column])){
            answer+=interval.second-interval.first+1;
            // Remove cells already covered by a horizontal trail.
            answer-=active.prefix(interval.second)-active.prefix(interval.first-1);
        }
    }
    cout<<answer<<'\n';
}