oj.uz

Submission #1012397

# Submission time Handle Problem Language Result Execution time Memory
1012397 2024-07-02T05:53:21 Z 12345678 Fish 3 (JOI24_fish3) C++17
20 / 100
 191 ms 33572 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=3e5+5;

ll n, d, c[nx], q, l[nx], r[nx], t[nx], qs[nx];
stack<pair<ll, ll>> st;
vector<ll> qrs[nx];

struct segtree
{
    ll d[4*nx];
    void update(int l, int r, int i, int idx, ll vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=vl, void();
        int md=(l+r)/2;
        update(l, md ,2*i, idx ,vl);
        update(md+1, r ,2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    ll query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>d;
    for (int i=1; i<=n; i++) cin>>c[i];
    for (int i=1; i<n; i++) if (c[i]>c[i+1]) t[i]=(c[i]-c[i+1])/d+((c[i]-c[i+1])%d!=0);
    for (int i=1; i<n; i++) qs[i]=qs[i-1]+t[i];
    for (int i=1; i<n; i++) s.update(1, n, 1, i, t[i]*i);
    cin>>q;
    for (int i=1; i<=q; i++)
    {
        cin>>l[i]>>r[i];
        if ((qs[r[i]-1]-qs[l[i]-1])*d>c[l[i]]) cout<<-1<<'\n';
        else
        {
            if (l[i]==r[i]) cout<<0<<'\n';
            else cout<<s.query(1, n, 1, l[i], r[i]-1)-(l[i]-1)*(qs[r[i]-1]-qs[l[i]-1])<<'\n';
        }
    }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 29196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 14160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 22868 KB Output is correct
2 Correct 158 ms 27772 KB Output is correct
3 Correct 112 ms 17732 KB Output is correct
4 Correct 174 ms 27984 KB Output is correct
5 Correct 167 ms 32632 KB Output is correct
6 Correct 186 ms 33572 KB Output is correct
7 Correct 169 ms 27732 KB Output is correct
8 Correct 183 ms 33356 KB Output is correct
9 Correct 113 ms 26996 KB Output is correct
10 Correct 84 ms 26860 KB Output is correct
11 Correct 165 ms 27988 KB Output is correct
12 Correct 127 ms 27216 KB Output is correct
13 Correct 180 ms 33364 KB Output is correct
14 Correct 101 ms 29268 KB Output is correct
15 Correct 191 ms 33168 KB Output is correct
16 Correct 95 ms 29268 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -