Escape Directions
National Olympiad — National round
Submission name: escapes.cpp
Problem summary
A square grid has L rows and L columns. Along each outer side N,S,E,W, inclusive intervals specify positions occupied by houses; intervals on the same side may overlap. From a cell, moving straight in one cardinal direction succeeds if that direction reaches a house. Count cells with exactly 1, 2, 3, and 4 successful directions. Count directions, not houses. Rows run north to south; columns west to east.
Input
L, then the four sides in order N,S,E,W. For each side: its interval count C, followed by C pairs l r.
Output
Four counts, corresponding to exactly 1,2,3,4 successful directions.
Constraints
1 ≤ L ≤ 10⁹; 1 ≤ l ≤ r ≤ L; 0 ≤ C ≤ 100,000 per side.
Worked example
An independently prepared example for this explanation.
Input
2 1 1 1 0 1 1 2 0
Output
2 2 0 0
Solution analysis
- Sweep the north and south intervals together. Track the number of active intervals separately on each side; a side contributes one direction whenever its active count is positive. Compute how many columns have 0,1,2 vertical escape directions.
- Perform the same sweep for east and west to obtain the counts of rows with 0,1,2 horizontal directions. A row/column pair has the sum of their counts, so multiply the two three-element histograms and accumulate by that sum.
Why it works
Whether north/south succeeds depends only on the column, and whether east/west succeeds depends only on the row. Every cell is exactly one such row/column pair. The sweep partitions the coordinate range into constant-coverage segments and counts their integer lengths, so the histogram products count every cell once.
Watch out. Treat r as inclusive by ending an interval at r+1. Overlapping houses on one side still provide only one direction. Cell counts require 64-bit integers.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Whether north/south succeeds depends only on the column, and whether east/west succeeds
// depends only on the row. Every cell is exactly one such row/column pair.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<array>
#include<iterator>
using namespace std;
using ll=long long;
array<ll,3>histogram(ll L,vector<array<ll,3>>events){
events.push_back({1,0,0});
events.push_back({L+1,0,0});
sort(events.begin(),events.end());
array<ll,3>ans{};
ll active[2]={0,0},prev=1;
for(size_t i=0;i<events.size();){
ll x=events[i][0];
ans[(active[0]>0)+(active[1]>0)]+=x-prev;
while(i<events.size()&&events[i][0]==x){
active[events[i][1]]+=events[i][2];
i++;
}
prev=x;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll L;
cin>>L;
vector<array<ll,3>>ev[2];
for(int side=0;side<4;side++){
int C;
cin>>C;
while(C--){
ll l,r;
cin>>l>>r;
ev[side/2].push_back({l,side%2,1});
ev[side/2].push_back({r+1,side%2,-1});
}
}
auto a=histogram(L,ev[0]),b=histogram(L,ev[1]);
ll ans[5]={};
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
ans[i+j]+=a[i]*b[j];
}
}
for(int k=1;k<=4;k++){
cout<<ans[k]<<' ';
}
cout<<'\n';
}