C - 都市計画と道路整備 / Urban Planning and Road Development Editorial by admin
Claude 4.6 Opus (Thinking)Overview
This problem involves performing \(Q\) construction operations that convert rectangular regions of vacant land into roads, and after each operation, determining the total number of “buildings facing a road.” We focus only on the boundary of the construction area and efficiently detect buildings adjacent to newly created road cells.
Analysis
Key Observations
Monotonic increase: Roads only increase (E→R), and once a building “faces a road,” it remains facing a road forever. Therefore, the counter only increases, making incremental updates effective.
Buildings are never inside the construction area: The problem guarantees that no buildings exist inside the construction area. Thus, buildings that could be affected by newly created road cells can only exist outside the construction rectangle and adjacent to its edges.
BBBBB ← Buildings may exist outside the top edge (row U-1)
RRRRR ← Top edge (row U): if this becomes a road, it affects buildings above
RRRRR ← Interior: all adjacent cells are inside the rectangle (no buildings) → no effect
RRRRR ← Bottom edge (row D)
BBBBB ← Buildings may exist outside the bottom edge (row D+1)
- Only the boundary needs to be checked: From the above observation, the cells to check are only those along the top, bottom, left, and right edges of the rectangle, totaling \(O(\text{perimeter})\) cells. The constraints guarantee that the total sum of perimeters is \(\leq 5 \times 10^6\).
Problem with the Naive Approach
Scanning the entire rectangle for each operation results in \(O(HW \times Q)\), which is too slow for \(HW \leq 2 \times 10^6\), \(Q \leq 10^5\).
Algorithm
Data Structures
Road intervals per row: For each row, we manage road cell intervals \([l, r]\) using
set<pair<int,int>>(sorted, no duplicates). This allows:- Checking whether a cell is a road in \(O(\log W)\) (
isRoad) - Efficiently enumerating “cells not yet roads (gaps)” within a range
- Merging new road intervals (
mergeInterval)
- Checking whether a cell is a road in \(O(\log W)\) (
facing array: A boolean for each building indicating whether it faces a road. The total count is managed with a counter
cnt.
Processing Steps for Each Operation
For an operation \([U, D] \times [L, R]\) (converted to 0-indexed):
Top edge (row \(U\)): Find cells in columns \([L, R]\) that are not yet roads from the interval set. For each such cell \((U, j)\), if the upper neighbor \((U-1, j)\) is an unmarked building, increment
cnt. If the rectangle is a single row, also check the lower neighbor. If at the left/right end, also check the outer side.Bottom edge (row \(D\), when \(U \neq D\)): Similarly, check the lower neighbor \((D+1, j)\).
Left edge (rows \(U{+}1\) to \(D{-}1\), column \(L\)): If the cell is a new road, check the left neighbor \((i, L{-}1)\). If the rectangle is a single column, also check the right side.
Right edge (when \(L \neq R\), column \(R\)): If the cell is a new road, check the right neighbor \((i, R{+}1)\).
Merge road intervals: For each row from \(U\) to \(D\), merge \([L, R]\) into the interval set.
Output
cnt.
Interval Merging (mergeInterval)
When adding \([l, r]\) to a row’s interval set, all overlapping or adjacent existing intervals are consolidated.
Existing: [2,4] [7,9] add [3,8]
→ Consolidated into [2,9]
Complexity
- Time complexity: \(O\!\left(HW + \displaystyle\sum_{k=1}^{Q} P_k \cdot \log W\right)\)
- \(P_k = 2(D_k - U_k + 1) + 2(R_k - L_k + 1)\) is the perimeter of the rectangle in the \(k\)-th operation
- The total sum of perimeters is \(\leq 5 \times 10^6\)
- The amortized cost of interval merging is \(O(HW)\) overall, since the number of intervals decreases each time intervals are consolidated
- Space complexity: \(O(HW)\) (grid, facing array, interval sets)
Implementation Notes
Conversion to 0-indexed: The input is 1-indexed, so don’t forget to apply
U--; D--; L--; R--;when reading input.Preventing double-counting at corners: When processing the left/right end cells on the top/bottom edges, to avoid overlap with left/right edge processing, the scan range for left/right edges is restricted to rows
U+1throughD-1.Enumerating gaps: The process of scanning the row’s interval set to find cells not yet roads within \([L, R]\) uses
lower_boundto locate the starting position and then collects gaps sequentially.Guard in
markBuilding: Out-of-bounds checks, building checks, and already-marked checks are performed together to prevent duplicate counting.Source Code
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int H,W,Q;
cin>>H>>W>>Q;
vector<string> grid(H);
for(int i=0;i<H;i++) cin>>grid[i];
// Per-row interval set of road columns (0-indexed)
// Using set<pair<int,int>> where each pair is [l,r] inclusive, sorted, non-overlapping
vector<set<pair<int,int>>> road(H);
// Initialize road intervals from grid
for(int i=0;i<H;i++){
int j=0;
while(j<W){
if(grid[i][j]=='R'){
int l=j;
while(j<W && grid[i][j]=='R') j++;
road[i].insert({l,j-1});
} else j++;
}
}
auto isRoad=[&](int i,int j)->bool{
if(i<0||i>=H||j<0||j>=W) return false;
auto it=road[i].upper_bound({j, INT_MAX});
if(it==road[i].begin()) return false;
--it;
return it->first<=j && j<=it->second;
};
// Track which buildings face road
vector<vector<bool>> facing(H, vector<bool>(W, false));
int cnt=0;
// Initial count
int dx[]={-1,1,0,0}, dy[]={0,0,-1,1};
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(grid[i][j]=='B'){
for(int d=0;d<4;d++){
int ni=i+dx[d], nj=j+dy[d];
if(ni>=0&&ni<H&&nj>=0&&nj<W&&grid[ni][nj]=='R'){
facing[i][j]=true;
cnt++;
break;
}
}
}
}
}
auto markBuilding=[&](int i,int j){
if(i>=0&&i<H&&j>=0&&j<W&&grid[i][j]=='B'&&!facing[i][j]){
facing[i][j]=true;
cnt++;
}
};
// Merge interval [l,r] into road[row], return which cells were newly added (on specified positions only)
auto mergeInterval=[&](int row, int l, int r){
auto it=road[row].lower_bound({l, -1});
if(it!=road[row].begin()){
--it;
if(it->second < l-1) ++it;
}
int nl=l, nr=r;
while(it!=road[row].end() && it->first<=r+1){
nl=min(nl, it->first);
nr=max(nr, it->second);
it=road[row].erase(it);
}
road[row].insert({nl,nr});
};
// Check if cell (i,j) was road before (we need to check before merging)
// We'll collect border cells, check, then merge
for(int q=0;q<Q;q++){
int U,D,L,R;
cin>>U>>D>>L>>R;
U--;D--;L--;R--; // 0-indexed
// Collect border cells and check which are newly becoming road
// Top border: row U, cols L..R -> check neighbor (U-1, j)
// Bottom border: row D, cols L..R -> check neighbor (D+1, j)
// Left border: rows U..D, col L -> check neighbor (i, L-1)
// Right border: rows U..D, col R -> check neighbor (i, R+1)
// Process top row
{
int i=U;
// find cells in [L,R] that are not yet road in row i
// then after marking, check (i-1,j) for building
vector<pair<int,int>> gaps;
auto it=road[i].lower_bound({L,-1});
if(it!=road[i].begin()){
--it;
if(it->second<L) ++it;
}
int cur=L;
while(it!=road[i].end() && it->first<=R){
if(cur < it->first){
gaps.push_back({cur, it->first-1});
}
cur=max(cur, it->second+1);
++it;
}
if(cur<=R) gaps.push_back({cur,R});
for(auto&[gl,gr]:gaps){
for(int j=gl;j<=gr;j++){
// cell (i,j) is newly road
markBuilding(i-1,j);
if(i==D) markBuilding(i+1,j);
if(j==L) markBuilding(i,j-1);
if(j==R) markBuilding(i,j+1);
}
}
}
// Process bottom row (if different from top)
if(D!=U){
int i=D;
vector<pair<int,int>> gaps;
auto it=road[i].lower_bound({L,-1});
if(it!=road[i].begin()){
--it;
if(it->second<L) ++it;
}
int cur=L;
while(it!=road[i].end() && it->first<=R){
if(cur < it->first){
gaps.push_back({cur, it->first-1});
}
cur=max(cur, it->second+1);
++it;
}
if(cur<=R) gaps.push_back({cur,R});
for(auto&[gl,gr]:gaps){
for(int j=gl;j<=gr;j++){
markBuilding(i+1,j);
if(j==L) markBuilding(i,j-1);
if(j==R) markBuilding(i,j+1);
}
}
}
// Process left column (rows U+1..D-1 if they exist, to avoid double counting corners)
{
int j=L;
for(int i=U+(D!=U?1:0); i<=D-(D!=U?1:0); i++){
if(!isRoad(i,j)){
markBuilding(i,j-1);
if(j==R) markBuilding(i,j+1);
}
}
}
// Process right column (if different from left)
if(R!=L){
int j=R;
for(int i=U+(D!=U?1:0); i<=D-(D!=U?1:0); i++){
if(!isRoad(i,j)){
markBuilding(i,j+1);
}
}
}
// Now merge [L,R] into all rows U..D
for(int i=U;i<=D;i++){
mergeInterval(i,L,R);
}
cout<<cnt<<'\n';
}
return 0;
}
This editorial was generated by claude4.6opus-thinking.
posted:
last update: