oj.uz

Submission #915864

# Submission time Handle Problem Language Result Execution time Memory
915864 2024-01-24T19:37:30 Z andrei_iorgulescu Cambridge (info1cup18_cambridge) C++14
100 / 100
 235 ms 14164 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 187 ms 12128 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 17 ms 6748 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 10 ms 4952 KB Output is correct
4 Correct 19 ms 5464 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 187 ms 12128 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 17 ms 6748 KB Output is correct
6 Correct 10 ms 4952 KB Output is correct
7 Correct 19 ms 5464 KB Output is correct
8 Correct 235 ms 13416 KB Output is correct
9 Correct 209 ms 13668 KB Output is correct
10 Correct 214 ms 13672 KB Output is correct
11 Correct 198 ms 14164 KB Output is correct
12 Correct 207 ms 13664 KB Output is correct
13 Correct 2 ms 4440 KB Output is correct