제출 #1358124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358124		KALARRY	Fish 3 (JOI24_fish3)	C++20	20 / 100	248 ms	45424 KiB

Main

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const long long INF = 1e15;

int N,Q;
long long D,a[300005];

struct Node
{
    int s = 0;
    bool problem = false;
    long long right_point;
    long long left_point;
    long long counter = 0;  
}st[1200005];

Node combine(Node left,Node right)
{
    Node ret;
    ret.s = left.s + right.s;
    ret.problem = left.problem | right.problem;
    ret.right_point = right.right_point;
    ret.counter = left.counter + right.counter;
    if(left.right_point <= right.left_point)
        ret.left_point = left.left_point;
    else
    {
        long long targ = (right.left_point/D)*D + left.right_point%D;
        if(targ > right.left_point)
            targ -= D;
        long long red = (left.right_point - targ)/D;
        ret.left_point = left.left_point - red*D;
        if(ret.left_point < 0)
            ret.problem = true;
        ret.counter += left.s * red;
    }
    return ret;
}

void build(int v = 1,int start = 1,int end = N)
{
    if(start==end)
    {
        st[v].s = 1;
        st[v].problem = 0;
        st[v].left_point = a[start];
        st[v].right_point = a[end];
        st[v].counter = 0;
        return;
    }
    int mid = (start + end)/2;
    build(2*v,start,mid);
    build(2*v+1,mid+1,end);
    st[v] = combine(st[2*v],st[2*v+1]);
}

Node query(int l,int r,int v = 1,int start = 1,int end = N)
{
    if(start==l && end==r)
        return st[v];
    int mid = (start + end)/2;
    if(r <= mid)
        return query(l,r,2*v,start,mid);
    else if(l > mid)
        return query(l,r,2*v+1,mid+1,end);
    else
        return combine(query(l,mid,2*v,start,mid),query(mid+1,r,2*v+1,mid+1,end));
}

int main()
{
    scanf("%d%lld",&N,&D);
    for(int i = 1 ; i <= N ; i++)
        scanf("%lld",&a[i]);
    build();
    scanf("%d",&Q);
    for(int l,r,i = 1 ; i <= Q ; i++)
    {
        scanf("%d%d",&l,&r);
        Node ans = query(l,r);
        if(ans.problem)
            printf("-1\n");
        else
            printf("%lld\n",ans.counter);
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d%lld",&N,&D);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
Main.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d%d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~

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