Intermediate.
Put your skills to the test.

Problem summary

Process star appearances and observations of the latest m stars. Average their coordinates with integer division toward zero, measure Manhattan distance from Earth, and find the minimum observed distance.

Source clarification. The printed bounds do not explicitly require an observation, but the requested minimum is undefined without one. This solution presumes at least one observation and does not invent an output convention for an all-star sequence.

Constraints

1 ≤ N ≤ 100000; coordinates −10^6…10^6; observations have at least m preceding stars.

Worked example

Input and output for the worked example discussed below.

8
1 1 2
1 2 0
1 2 2
2 2
1 3 5
2 3
1 -3 -3
2 2

1

Solution analysis

1. Store separate coordinate prefix sums over stars only. Civilization events do not extend those arrays. With s stars, the latest m sums are prefix[s]−prefix[s−m].
2. Divide the two signed sums by m, using C++ integer division toward zero. Then compute |x|+|y| and update a running minimum. Prefix sums need long long because many coordinates accumulate.
3. The sample observations estimate (2,1), then (2,2), then (0,1), whose Manhattan distances are 3,4,1. Therefore the historical minimum is 1. The all-star case has no mathematically defined minimum and is not assigned an invented stdout value.

Why it works

Prefix subtraction recovers exactly the most recent m star coordinates. Their specified integer means and Manhattan distance are evaluated directly. The smallest of these exact observations is the required minimum.

Watch out. Use signed 64-bit sums and truncation toward zero, not floor for negatives. Count stars separately from all events. At least one observation is needed to define the minimum.

An independently written complete program with standard headers.

#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int events;
    cin>>events;
    vector<long long>x(1,0);
    vector<long long>y(1,0);
    long long answer=numeric_limits<long long>::max();
    bool observed=false;
    for(int i=0;i<events;i++){
        int type;
        cin>>type;
        if(type==1){
            long long a;
            long long b;
            cin>>a>>b;
            x.push_back(x.back()+a);
            y.push_back(y.back()+b);
        }
        else{
            int count;
            cin>>count;
            int stars=int(x.size())-1;
            // C++ signed division provides the specified integer averages.
            long long a=(x[stars]-x[stars-count])/count;
            long long b=(y[stars]-y[stars-count])/count;
            answer=min(answer,llabs(a)+llabs(b));
            observed=true;
        }
    }
    if(observed){
        cout<<answer<<'\n';
    }
}