QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	Submission ID	Problem	Hacker	Owner	Result	Submit time	Judge time
#1164	#725998	#9601. I Wanna Maker	chzhc_	TheZone	Failed.	2024-11-11 00:43:17	2024-11-11 00:43:18

Details

Extra Test:

Accepted

time: 0ms

memory: 3712kb

input:

output:

result:

ok single line: '2'

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#725998	#9601. I Wanna Maker	TheZone	AC ✓	54ms	6756kb	C++20	2.7kb	2024-11-08 21:10:11	2024-11-08 21:10:11

answer

#include<bits/stdc++.h>
#define N 200010
#define ll long long
#define pll pair<ll,ll>
#define fi first 
#define se second
using namespace std;
int T,n;
ll k,x,lm,rm,l,r;
pll p[N];

void solve(){
    ll pl=0,pr=1e9;
    while(pl<pr){
        ll mid=(pl+pr+1)/2;
        if(k*(2*mid+k-1)/2>x) pr=mid-1;
        else pl=mid;
    }
    l=pl;
    pl=0;pr=1e9;
    while(pl<pr){
        ll mid=(pl+pr)/2;
        if(k*(2*mid-k+1)/2<x) pl=mid+1;
        else pr=mid;
    }
    r=pl;
    // cout<<l<<' '<<r<<" !!!\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        cin>>n;
        int cnt=0;
        lm=1e9;
        rm=0;
        for(int i=1;i<=n;i++){
            int t;
            cin>>t>>k>>x;
            solve();
            if(t==1){
                lm=min(l,lm);
                rm=max(r,rm);
                continue;
            }
            cnt++;
            p[cnt].fi=l;
            p[cnt].se=r;
        }
        if(!lm){
            cout<<"0\n";
            continue;
        }
        if(!cnt){
            cout<<"-1\n";
            continue;
        }
        cnt++;
        p[cnt].fi=lm;
        p[cnt].se=1e18;
        sort(p+1,p+cnt+1);
        ll ans=0,rx=1e18;
        // cout<<lm<<' '<<rm<<" !!\n";
        for(int i=cnt;i>=1;i--){
            rx=min(rx,p[i].se);
            // cout<<i<<' '<<p[i].fi<<' '<<p[i].se<<" !!\n"; 
            if(p[i].fi>lm) continue;
            if(p[i].fi>p[i-1].fi&&rx==1e18){
                ans=-1;
                break; 
            }
            ans+=(p[i].fi-p[i-1].fi)*max(0ll,rx-rm);
        }
        cout<<ans<<'\n';
    }
    return 0;
}
/*#include<bits/stdc++.h>
#define N 200010
#define ll long long
#define pll pair<ll,ll>
#define fi first 
#define se second
using namespace std;
int T,n;
ll k,x,lm,rm,l,r;
pll p[N];

void solve(){
    ll pl=0,pr=1e9;
    while(pl<pr){
        ll mid=(pl+pr+1)/2;
        if(k*(2*mid+k-1)/2>x) pr=mid-1;
        else pl=mid;
    }
    l=pl;
    pl=0;pr=1e9;
    while(pl<pr){
        ll mid=(pl+pr)/2;
        if(k*(2*mid-k+1)/2<x) pl=mid+1;
        else pr=mid;
    }
    r=pl;
    // cout<<l<<' '<<r<<" !!!\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        cin>>n;
        int cnt=0;
        lm=1e9;
        rm=0;
        for(int i=1;i<=n;i++){
            int t;
            cin>>t>>k>>x;
            solve();
            if(t==1){
                lm=min(l,lm);
                rm=max(r,rm);
                continue;
            }
            cnt++;
            p[cnt].fi=l;
        cout<<ans<<'\n';
    }
    return 0;
}*/

Source code, Language: C++20