算法

(暴力枚举) $O(n)$

维护每个区间的最高点和最低点即可。

参考文献

y总的课

C++ 代码

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1000001,inf=0x7f7f7f7f;
int n,ans[N],f,u,d,l;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>f;
    fs(i,1,n,1){
        int x,a,b;cin>>x>>a>>b;
        a++,b--;
        u+=x-l;
        d-=x-l;
        if((u&1)!=(b&1)) b--;
        if((d&1)!=(a&1)) a++;
        u=min(u,b);
        d=max(d,a);
        if(u<d){
            cout<<"Stupid bird!";
            return 0;
        }
        ans[i]=(x+d)/2;
        l=x;
    }
    fs(i,1,n,1) cout<<ans[i]<<'\n';
    cout<<ans[n];
    return 0;
}