oj.uz

Submission #1012395

# Submission time Handle Problem Language Result Execution time Memory
1012395 2024-07-02T05:51:29 Z 12345678 Fish 3 (JOI24_fish3) C++17
20 / 100
 345 ms 57964 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], sm;
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';
}

/*
5 1
5 4 3 2 1
3
1 2
2 4
1 5

5 1
3 1 4 1 5
3 
1 5 
2 4 
3 5

5 5
1 2 3 4 5
3
1 2
2 3
1 5

3 1
1 2 1
1
1 3
*/

Subtask #1
0 / 9.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 28712 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 302 ms 42320 KB Output is correct
2 Correct 317 ms 51312 KB Output is correct
3 Correct 210 ms 36180 KB Output is correct
4 Correct 303 ms 54600 KB Output is correct
5 Correct 327 ms 56784 KB Output is correct
6 Correct 299 ms 57964 KB Output is correct
7 Correct 275 ms 47948 KB Output is correct
8 Correct 306 ms 57936 KB Output is correct
9 Correct 250 ms 50516 KB Output is correct
10 Correct 221 ms 50260 KB Output is correct
11 Correct 319 ms 54608 KB Output is correct
12 Correct 276 ms 53788 KB Output is correct
13 Correct 345 ms 57940 KB Output is correct
14 Correct 226 ms 53488 KB Output is correct
15 Correct 313 ms 57556 KB Output is correct
16 Correct 222 ms 53588 KB Output is correct

Subtask #5
0 / 36.0

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