提出 cbc76b20-266b-4fbe-b4b0-bf2ec046d7b7

コード

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
const ll MAX=(1ll<<31)-1;
using P=pair<ll,ll>;
P op(P a,P b){
    P p=crt({a.first,b.first},{a.second,b.second});
    if(p.first>MAX||p.second==0){
        p.first=MAX+1;
        p.second=MAX+2;
    }
    if(p.second>MAX+2)
        p.second=MAX+2;
    return p;
}
vector<P>vec;
P prod(int l,int r){
    P res=vec[l];
    for(int i=l+1;i<r;i++){
        res=op(res,vec[i]);
        if((res.first?res.first:res.second)>MAX)
            break;
    }
    return res;
}
int main(){
    int n,a,b,q,l,r;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        vec.push_back(P(a,b));
    }
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>l>>r;
        l--;
        P p=prod(l,r);
        if(p.first==0)
            p.first=p.second;
        if(p.first>MAX)
            cout<<-1<<endl;
        else
            cout<<p.first<<endl;
    }
}

結果

問題	点数	言語	結果	実行時間	メモリ
I. Segment CRT	50	C++ (gcc)	TLE	2101 ms	5400 KiB