Submission #1272766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272766		ghammazhassan	Fish 3 (JOI24_fish3)	C++20	0 / 100	367 ms	37204 KiB

Main

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define endl "\n"
#define fi first
#define se second
const int M=998244353;
const int inf = 1e14;
const int LOG=20;
const int N=3e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
struct node{
    int mx=0,sm=0,mn=inf;
};
node join(node x,node y){
    node r;
    r.mx=max(x.mx,y.mx);
    r.mn=min(x.mn,y.mn);
    r.sm=x.sm+y.sm;
    return r;
}
node seg[4*N];
int a[N],b[N],vi[N],di[N];
void build(int s=1,int e=n+1,int v=1){
    if (e-s==1){
        seg[v].mx=vi[s];
        seg[v].sm=di[s];
        seg[v].mn=di[s];
        return;
    }
    int li=2*v;
    int ri=2*v+1;
    int m=(s+e)/2;
    build(s,m,li);
    build(m,e,ri);
    seg[v]=join(seg[li],seg[ri]);
}
node query(int l,int r,int s=1,int e=n+1,int v=1){
    if (l<=s and e<=r){
        return seg[v];
    }
    if (r<=s or l>=e){
        node p;
        return p;
    }
    int li=2*v;
    int ri=2*v+1;
    int m=(s+e)/2;
    return join(query(l,r,s,m,li),query(l,r,m,e,ri));
}
void solve()
{   
    cin >> n >> x;
    for (int i=1;i<=n;i++){
        cin >> a[i];
        b[i]=a[i]-(a[i]/x)*x;
        int u=max(0ll,(b[i-1]-b[i]+x-1)/x);
        b[i]+=u*x;
        di[i]=a[i]-b[i];
        if (b[i]>a[i]){
            vi[i]=1;
        }
    }
    build();
    cin >> q;
    for (int o=0;o<q;o++){
        cin >> l >> r;
        if (query(l+1,r+1).mx){
            cout << -1 << endl;
            continue;
        }
        node p=query(l,r+1);
        cout << (p.sm-p.mn*(r-l+1))/x << endl;
    }

    
}
signed main()    
{

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
} 

• Subtask 1: 0 / 9
• Subtask 2: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36