Submission #998375

#	Time	Username	Problem	Language	Result	Execution time	Memory
998375		vladilius	Food Court (JOI21_foodcourt)	C++17	14 / 100	1106 ms	260768 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const ll inf = numeric_limits<ll> :: max();
 
struct STB{
    vector<ll> a;
    // a[i] += x (l <= i <= r)
    // a[i] = max(a[i], x) (l <= i <= r)
    // ? a[i]
    int n;
    STB(int ns){
        n = ns;
        a.resize(n + 1);
    }
    void add(int l, int r, ll x){
        for (int i = l; i <= r; i++){
            a[i] += x;
        }
    }
    void chmax(int l, int r, ll x){
        for (int i = l; i <= r; i++){
            a[i] = max(a[i], x);
        }
    }
    ll get(int p){
        return a[p];
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, m, q; cin>>n>>m>>q;
    STB C(n);
    const int S = sqrt(n);
    const int sz = (int) ceil(1.0 * n / S) - 1;
    vector<int> st[n + 1], st1[sz + 5];
    vector<ll> pr[n + 1], pr1[sz + 5];
    
    vector<int> bc(n + 1);
    int i = 1, j = S, k = 0;
    while (i <= n){
        while (i <= j) bc[i++] = k;
        j = min(n, j + S);
        k++;
    }
 
    vector<int> col(q + 1);
    map<int, bool> mp;
    for (int tt = 1; tt <= q; tt++){
        int type; cin>>type;
        if (type == 1){
            int l, r, c, k; cin>>l>>r>>c>>k;
            col[tt] = c;
            mp[tt] = 1;
            C.add(l, r, k);
            int bl = bc[l] + 1, br = bc[r] - 1;
            if (bl > br){
                for (int i = l; i <= r; i++){
                    st[i].pb(tt);
                    if (pr[i].empty()) pr[i].pb(k);
                    else pr[i].pb(pr[i].back() + k);
                }
                continue;
            }
            for (int i = bl; i <= br; i++){
                st1[i].pb(tt);
                if (pr1[i].empty()) pr1[i].pb(k);
                else pr1[i].pb(pr1[i].back() + k);
            }
            for (int i = l; i <= S * bl; i++){
                st[i].pb(tt);
                if (pr[i].empty()) pr[i].pb(k);
                else pr[i].pb(pr[i].back() + k);
            }
            for (int i = S * (br + 1) + 1; i <= r; i++){
                st[i].pb(tt);
                if (pr[i].empty()) pr[i].pb(k);
                else pr[i].pb(pr[i].back() + k);
            }
        }
        else if (type == 2){
            int l, r, k; cin>>l>>r>>k;
            C.add(l, r, -k);
            C.chmax(1, n, 0);
        }
        else {
            int a; ll b; cin>>a>>b;
            ll v = C.get(a);
            if (b > v){
                cout<<0<<"\n";
                continue;
            }
            b -= v;
            if (!pr1[bc[a]].empty()) b += pr1[bc[a]].back();
            if (!pr[a].empty()) b += pr[a].back();
            
            auto low = [&](vector<int>& x, int t){
                if (x.empty() || x[0] > t) return -1;
                int l = 0, r = (int) x.size() - 1;
                while (l + 1 < r){
                    int m = (l + r) / 2;
                    if (x[m] <= t){
                        l = m;
                    }
                    else {
                        r = m - 1;
                    }
                }
                if (x[r] <= t) l = r;
                return l;
            };
            
            auto check = [&](int m){
                int j1 = low(st1[bc[a]], m);
                int j2 = low(st[a], m);
                ll val = 0;
                if (j1 >= 0) val += pr1[bc[a]][j1];
                if (j2 >= 0) val += pr[a][j2];
                return (val >= b);
            };
            
            int l = 1, r = tt;
            while (l + 1 < r){
                int m = (l + r) / 2;
                if (check(m)){
                    r = m;
                }
                else {
                    l = m + 1;
                }
            }
            if (check(l)) r = l;
            if (mp.find(r) == mp.end()){
                while (true){
                    l++;
                }
            }
            cout<<col[r]<<"\n";
        }
    }
}

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