Submission #915864

#	Time	Username	Problem	Language	Result	Execution time	Memory
915864		andrei_iorgulescu	Cambridge (info1cup18_cambridge)	C++14	100 / 100	235 ms	14164 KiB

cambridge

#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;

struct ura
{
    int t,d,idx;
};

struct aint_node
{
    int lazy,maxim;
};

bool cmp(ura A,ura B)
{
    return A.d < B.d;
}

int n,m;
ura a[100005];
int unde[100005];
int maxr[100005];
aint_node aint[400005];

void build(int nod,int l,int r)
{
    aint[nod].lazy = 0;
    aint[nod].maxim = -inf;
    if (l != r)
    {
        int mij = (l + r) / 2;
        build(2 * nod,l,mij);
        build(2 * nod + 1,mij + 1,r);
    }
}

void prop_lazy(int nod,int l,int r)
{
    if (l == r)
        return;
    aint[2 * nod].maxim += aint[nod].lazy;
    aint[2 * nod + 1].maxim += aint[nod].lazy;
    aint[2 * nod].lazy += aint[nod].lazy;
    aint[2 * nod + 1].lazy += aint[nod].lazy;
    aint[nod].lazy = 0;
}

void update(int nod,int l,int r,int st,int dr,int val)
{
    prop_lazy(nod,l,r);
    if (dr < l or r < st)
        return;
    if (st <= l and r <= dr)
    {
        aint[nod].lazy += val;
        aint[nod].maxim += val;
        return;
    }
    int mij = (l + r) / 2;
    update(2 * nod,l,mij,st,dr,val);
    update(2 * nod + 1,mij + 1,r,st,dr,val);
    aint[nod].maxim = max(aint[2 * nod].maxim,aint[2 * nod + 1].maxim);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].t >> a[i].d;
        a[i].idx = i;
    }
    sort(a + 1,a + n + 1,cmp);
    for (int i = 1; i <= n; i++)
        unde[a[i].idx] = i;
    build(1,1,n);
    int r = 0;
    for (int i = 1; i <= n; i++)
    {
        while (r < n and aint[1].maxim < 0)
        {
            r++;
            int pz = unde[r];
            //cout << r << ' ' << pz << ' ' << aint[1].maxim << endl;
            update(1,1,n,pz,n,a[pz].t);
            update(1,1,n,pz,pz,inf - a[pz].d);
            if (aint[1].maxim >= 0)
            {
                update(1,1,n,pz,n,-a[pz].t);
                update(1,1,n,pz,pz,-inf + a[pz].d);
                r--;
                break;
            }
        }
        maxr[i] = r;
        //cout << r << ' ';
        int pz = unde[i];
        update(1,1,n,pz,n,-a[pz].t);
        update(1,1,n,pz,pz,-inf + a[pz].d);
    }
    for (int i = 1; i <= m; i++)
    {
        int l,r;
        cin >> l >> r;
        if (maxr[l] >= r)
            cout << 1 << '\n';
        else
            cout << 0 << '\n';
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 15 / 15
• Subtask 4: 45 / 45