Submission #994909

#	Time	Username	Problem	Language	Result	Execution time	Memory
994909		prvocislo	Fish 3 (JOI24_fish3)	C++17	100 / 100	515 ms	65212 KiB

Main

// He was a moth to the flame
// She was holding the matches
// Soon, she's gonna find stealing other people's toys
// On the playground won't make you many friends

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

struct sgttree // range add, range sum
{
    vector<ll> st, lz; 
    vector<int> l, r;
    void init(int n)
    {
        int n2 = 1;
        while (n2 <= n) n2 <<= 1;
        st.assign(n2 * 2, 0), lz.assign(n2 * 2, 0), l.assign(n2 * 2, 0), r.assign(n2 * 2, 0);
        for (int i = n2; i < n2 * 2; i++) l[i] = r[i] = i - n2;
        for (int i = n2 - 1; i > 0; i--) l[i] = l[i * 2], r[i] = r[i * 2 + 1];
    }
    void upd(int vr, ll x)
    {
        st[vr] += ((ll)(r[vr] - l[vr] + 1)) * x, lz[vr] += x;
    }
    void unlazy(int vr)
    {
        upd(vr * 2, lz[vr]), upd(vr * 2 + 1, lz[vr]);
        lz[vr] = 0;
    }
    void update(int li, int ri, ll x, int vr = 1)
    {
        if (ri < l[vr] || r[vr] < li) return;
        if (li <= l[vr] && r[vr] <= ri) 
            return upd(vr, x), void();
        unlazy(vr);
        update(li, ri, x, vr * 2), update(li, ri, x, vr * 2 + 1);
        st[vr] = st[vr * 2] + st[vr * 2 + 1];
    }
    ll query(int li, int ri, int vr = 1)
    {
        if (ri < l[vr] || r[vr] < li) return 0;
        if (li <= l[vr] && r[vr] <= ri) return st[vr];
        unlazy(vr);
        return query(li, ri, vr * 2) + query(li, ri, vr * 2 + 1);
    }
};
struct block // lx az rx, na poziciach li az ri
{
    int li, ri;
    ll lx, rx;
};
struct query
{
    int l, r, i;
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q; ll d;
    cin >> n >> d;
    vector<ll> c(n);
    for (int i = 0; i < n; i++) cin >> c[i];
    cin >> q;
    vector<ll> ans(q);
    vector<vector<query> > qu(n);
    for (int i = 0; i < q; i++)
    {
        query qi;
        cin >> qi.l >> qi.r, qi.l--, qi.r--, qi.i = i;
        qu[qi.r].push_back(qi);
    }
    sgttree st; st.init(n);
    vector<block> s;
    for (int i = 0; i < n; i++)
    {
        block nw;
        nw.li = nw.ri = i, nw.lx = nw.rx = c[i];
        while (s.size() && s.back().rx > nw.lx)
        {
            block b = s.back();
            ll sub = (b.rx - nw.lx + d - 1) / d;
            s.pop_back();
            st.update(b.li, b.ri, sub);
            nw.li = b.li, nw.lx = b.lx - sub * d;
        }
        s.push_back(nw);
        for (query qi : qu[i])
        {
            ll lf = c[qi.l] - st.query(qi.l, qi.l) * d;
            if (lf < 0) ans[qi.i] = -1;
            else ans[qi.i] = st.query(qi.l, qi.r);
        }
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
    return 0;
}

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