CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) D. Climbing the Tree

深藏阁楼爱情的钟 2024-03-24 12:59 25阅读 0赞

[Problems - Codeforces][]

题意：

![99e173500b7946a4b9dc13783292652e.png][]

思路：

![6a492ef7fb5a41668e98ce02095bb9b5.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e5+10;
    const int mxe=5e4+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    
    vector<int> v;
    int q,op,a,b,n,L=-Inf,R=Inf;
    int get(int L,int a,int b){
        int res=0;
        if(L<=a) res=1;
        else{
            int up=(L-a),down=(a-b);
            res=(up+down-1)/down+1ll;
        }
        return res;
    }
    void solve(){
        v.clear();
        L=-Inf,R=Inf;
        cin>>q;
        while(q--){
            cin>>op;
            if(op==1){
                cin>>a>>b>>n;
                int l,r;
                if(n==1) l=1,r=a;
                else{
                    l=(n-2)*(a-b)+a+1;
                    r=(n-1)*(a-b)+a;
                }
                if(r<L||l>R){
                    v.push_back(0);
                }else{
                    L=max(L,l);
                    R=min(R,r);
                    v.push_back(1);
                }
            }else{
                cin>>a>>b;
                int ans1=get(L,a,b),ans2=get(R,a,b);
                if(ans1!=ans2) v.push_back(-1);
                else v.push_back(ans1);
            }
        }
        for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problems - Codeforces]: https://codeforces.com/contest/1810/problems
[99e173500b7946a4b9dc13783292652e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6bbc4818b31343be92e801d3e603e0d8.png
[6a492ef7fb5a41668e98ce02095bb9b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/43e33a70a4ba472f9cb20d447c3518d9.png