Submission #898017

#	Time	Username	Problem	Language	Result	Execution time	Memory
898017		12345678	Fountain (eJOI20_fountain)	C++17	100 / 100	147 ms	15240 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;
int n, q, w[nx], sz[nx], ans[2*nx], p, x;
vector<pair<int, int>> d[nx];
stack<int> st;

struct segtree
{
    int d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        if (l==r) return d[i]+=lz[i], lz[i]=0, void();
        lz[2*i]+=lz[i];
        lz[2*i+1]+=lz[i];
        d[i]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, int 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]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int vl)
    {
        pushlz(l, r, i);
        if (l==r) return l;
        int md=(l+r)/2;
        pushlz(l, md, 2*i);
        pushlz(md+1, r, 2*i+1);
        if (d[2*i]>=vl) return query(l, md, 2*i, vl);
        else return query(md+1, r, 2*i+1, vl);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>w[i]>>sz[i];
    w[n+1]=sz[n+1]=1e9;
    for (int i=1; i<=q; i++) cin>>p>>x, d[p].push_back({x, i});
    for (int i=n+1; i>=1; i--)
    {
        while (!st.empty()&&w[st.top()]<=w[i]) s.update(1, n+1, 1, st.top(), n+1, -sz[st.top()]), st.pop();
        s.update(1, n+1, 1, i, n+1, sz[i]);
        st.push(i);
        for (auto [x, idx]:d[i]) ans[idx]=s.query(1, n+1, 1, x);
    }
    for (int i=1; i<=q; i++) cout<<((ans[i]==n+1)?0:ans[i])<<'\n';
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40