oj.uz

Submission #1012396

# Submission time Handle Problem Language Result Execution time Memory
1012396 2024-07-02T05:52:53 Z 12345678 Fish 3 (JOI24_fish3) C++17
20 / 100
 378 ms 46676 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], res[nx];
stack<pair<ll, ll>> st;
vector<ll> qrs[nx];

struct segtree
{
    ll d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i]+=lz[i]*(r-l+1);
        if (l==r) return lz[i]=0, void();
        lz[2*i]+=lz[i];
        lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md ,2*i, ql, qr, vl);
        update(md+1, r ,2*i+1, ql, qr, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    ll query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        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);
    }
    void show(int l, int r, int i)
    {
        pushlz(l, r, i);
        if (l==r) cout<<l<<' '<<r<<' '<<d[i]<<'\n';
        if (l==r) return;
        int md=(l+r)/2;
        show(l, md ,2*i);
        show(md+1, r, 2*i+1);
    }
} 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++) cout<<i<<' '<<t[i]<<'\n';
    cin>>q;
    for (int i=1; i<=q; i++) cin>>l[i]>>r[i], qrs[r[i]].push_back(i);
    for (int i=1; i<=n; i++)
    {
        //cout<<"debug "<<i<<'\n';
        //s.show(1, n, 1);
        //cout<<'\n';
        for (auto x:qrs[i])
        {
            if (s.query(1, n, 1, l[x], l[x])*d>c[l[x]]) res[x]=-1;
            else res[x]=s.query(1, n, 1, l[x], r[x]-1);
        }
        s.update(1, n, 1, 1, i, t[i]);
    }
    for (int i=1; i<=q; i++) cout<<res[i]<<'\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 290 ms 42848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 19796 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 320 ms 32340 KB Output is correct
2 Correct 339 ms 41300 KB Output is correct
3 Correct 208 ms 25172 KB Output is correct
4 Correct 336 ms 41280 KB Output is correct
5 Correct 378 ms 45880 KB Output is correct
6 Correct 344 ms 46676 KB Output is correct
7 Correct 279 ms 37200 KB Output is correct
8 Correct 301 ms 46672 KB Output is correct
9 Correct 252 ms 40528 KB Output is correct
10 Correct 233 ms 40192 KB Output is correct
11 Correct 353 ms 41300 KB Output is correct
12 Correct 268 ms 40532 KB Output is correct
13 Correct 325 ms 46672 KB Output is correct
14 Correct 267 ms 42412 KB Output is correct
15 Correct 340 ms 46676 KB Output is correct
16 Correct 231 ms 42580 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 -