Submission #1047648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047648		Andrey	Food Court (JOI21_foodcourt)	C++14	68 / 100	205 ms	87660 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;

vector<pair<pair<long long,long long>,long long>> haha[250001];
vector<pair<long long,long long>> bruh[250001];
vector<long long> seg(1000001);
vector<long long> wow(1000001);
vector<long long> idk(500001);
vector<long long> troll(500001);

long long calc3(long long a) {
    long long c = 0,ans = 0;
    for(long long i = 19; i >= 0; i--) {
        if(c+(1 << i) <= a) {
            c+=(1 << i);
            ans+=troll[c];
        }
    }
    return ans;
}

void upd2(long long a, long long x, bool yo) {
    while(a < idk.size()) {
        if(yo) {
            idk[a]+=x;
        }
        else {
            troll[a]+=x;
        }
        a+=(a&(-a));
    }
}

long long dude(long long br) {
    long long c = 0;
    for(long long i = 19; i >= 0; i--) {
        if(c+(1 << i) < idk.size() && idk[c+(1 << i)] < br) {
            c+=(1 << i);
            br-=idk[c];
        }
    }
    return c;
}

void upd(long long l, long long r, long long ql, long long qr, long long x, long long br) {
    if(qr < ql) {
        return;
    }
    if(l == ql && r == qr) {
        seg[x]+=br;
        wow[x]+=br;
        return;
    }
    int mid = (l+r)/2;
    if(qr <= mid) {
        upd(l,mid,ql,qr,x*2,br);
    }
    else if(ql > mid) {
        upd(mid+1,r,ql,qr,x*2+1,br);
    }
    else {
        upd(l,mid,ql,mid,x*2,br);
        upd(mid+1,r,mid+1,qr,x*2+1,br);
    }
    seg[x] = min(seg[x*2],seg[x*2+1]);
    seg[x]+=wow[x];
}

long long calc(long long l, long long r, long long ql, long long qr, long long x) {
    if(l == ql && r == qr) {
        return seg[x];
    }
    long long ans = 0;
    long long mid = (l+r)/2;
    if(qr <= mid) {
        ans = calc(l,mid,ql,qr,x*2);
    }
    else if(ql > mid) {
        ans = calc(mid+1,r,ql,qr,x*2+1);
    }
    else {
        ans = min(calc(l,mid,ql,mid,x*2),calc(mid+1,r,mid+1,qr,x*2+1));
    }
    return ans+wow[x];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,m,q;
    cin >> n >> m >> q;
    vector<long long> col(q+1);
    for(long long i = 1; i <= q; i++) {
        long long t,l,r,x,br;
        cin >> t;
        if(t == 1) {
            cin >> l >> r >> x >> br;
            haha[l].push_back({{i,br},0});
            haha[r+1].push_back({{i,-br},0});
            col[i] = x;
        }
        else if(t == 2) {
            cin >> l >> r >> br;
            haha[l].push_back({{i,-br},1});
            haha[r+1].push_back({{i,br},1});
        }
        else {
            cin >> l >> br;
            bruh[l].push_back({i,br});
        }
    }
    vector<long long> ans(q+1,-1);
    for(long long i = 1; i <= n; i++) {
        for(pair<pair<long long,long long>,long long> v: haha[i]) {
            long long p = v.first.first,c = v.first.second;
            upd(1,q,p,q,1,c);
            if(v.second) {
                upd2(p,-c,0);
            }
            else {
                upd2(p,c,1);
            }
        }
        for(pair<long long,long long> v: bruh[i]) {
            long long br = v.second;
            br+=calc3(v.first);
            br+=min(0LL,calc(1,q,1,v.first,1));
            long long c = dude(br);
            if(c >= v.first) {
                ans[v.first] = 0;
            }
            else {
                ans[v.first] = col[c+1];
            }
        }
    }
    for(long long i = 1; i <= q; i++) {
        if(ans[i] != -1) {
            cout << ans[i] << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'void upd2(long long int, long long int, bool)':
foodcourt.cpp:23:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     while(a < idk.size()) {
      |           ~~^~~~~~~~~~~~
foodcourt.cpp: In function 'long long int dude(long long int)':
foodcourt.cpp:37:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if(c+(1 << i) < idk.size() && idk[c+(1 << i)] < br) {
      |            ~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 0 / 11