Submission #1369421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1369421		solution6312	Legendary Dango Eater (JOI26_dango)	C++17	0 / 100	350 ms	1792 KiB

Main

#include <iostream>
#include <cassert>
using namespace std;
using ll=long long;

const int MN=5e5+13, ML=22;
const int inf32=1e9;
int N, Q; ll K;
ll A[MN], pre[MN];
int nxt[MN][ML]; ll wgt[MN][ML];

int main()
{
    cin>>N>>Q>>K;
    for (int i=1; i<=N; i++)
    {
        cin>>A[i];
        if (i&1) pre[i]=pre[i-1]+A[i];
        else pre[i]=pre[i-1]-A[i];
    }
    //pre[N+2]=pre[N+1]=pre[N];
    for (int x=1; x<=N; x+=2)
    {
        int y=x;
        while (y+2<=N && (pre[y]-pre[x-1])%K>=A[y+1])
        {
            y+=2;
            assert(pre[y]>=pre[x-1]);
        }
        wgt[x][0]=(pre[y]-pre[x-1])/K;
        nxt[x][0]=y;
        //cerr<<x<<" TO "<<y<<": "<<wgt[x][0]<<endl;
    }
    for (int j=1; j<ML; j++)
    {
        for (int i=1; i<=N; i++)
        {
            if (nxt[i][j-1]+2>N) nxt[i][j]=inf32;
            else
            {
                nxt[i][j]=nxt[nxt[i][j-1]+2][j-1];
                wgt[i][j]=wgt[i][j-1]+wgt[nxt[i][j-1]+2][j-1];
            }
        }
    }
    while (Q--)
    {
        int L, R; cin>>L>>R;
        if (!(L&1)) L++;
        if (!(R&1)) R--;
        if (L>R)
        {
            cout<<0<<endl;
            continue;
        }
        ll ans=0;
        for (int i=ML-1; i>=0; i--)
        {
            //cerr<<L<<' '<<i<<": "<<nxt[L][i]<<' '<<wgt[L][i]<<endl;
            assert(L&1);
            if (L<=N && nxt[L][i]<=R)
            {
                ans+=wgt[L][i];
                L=nxt[L][i]+2;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 5
• Subtask 3: 0 / 18
• Subtask 4: 0 / 27
• Subtask 5: 0 / 17
• Subtask 6: 0 / 27