Submission #797861

#	Time	Username	Problem	Language	Result	Execution time	Memory
797861		vjudge1	Food Court (JOI21_foodcourt)	C++17	100 / 100	532 ms	372748 KiB

foodcourt

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1<<18;

ll sum[N<<1], mn[N<<1];
    
void update(int pos, int val, int x, int lx, int rx) {
    if(lx + 1 == rx) {
        sum[x] += val;
        mn[x] = sum[x];
        return;
    }
    int m = (lx + rx) / 2;
    pos < m ? 
    update(pos, val, x * 2 + 1, lx, m) :
    update(pos, val, x * 2 + 2, m, rx) ;
    sum[x] = sum[x * 2 + 1] + sum[x * 2 + 2];
    mn[x] = min(mn[x * 2 + 1], sum[x * 2 + 1] + mn[x * 2 + 2]);
}

pair < ll, ll > get(int pos, int x, int lx, int rx) {
    if(pos < lx) {
        return {0, 0};
    }  
    if(rx <= pos + 1) {
        return {mn[x], sum[x]};
    }
    int m = (lx + rx) / 2;
    pair < ll, ll > L = get(pos, x * 2 + 1, lx, m);
    pair < ll, ll > R = get(pos, x * 2 + 2, m, rx);
    return {min(L.first, R.first + L.second), L.second + R.second};
}

ll get(int pos) {
    pair < ll, ll > X = get(pos, 0, 0, N);
    return X.second + (X.first < 0 ? -X.first : 0ll);
}

ll tree[N];

void update(int x, ll val) {
    for(; x < N; tree[x] += val, x += -x&x);
}

ll Sum(int x) {
    ll ans = 0;
    for(; x; ans += tree[x], x ^= -x&x);
    return ans;
}

int find(ll k) {
    int l = 0, r = N, m;
    for(; l + 1 < r;) {
        m = (l + r) / 2;
        (Sum(m) < k ? l : r) = m;
    }
    return r;
}

int Query[N];
queue < pair < int, int > > Time[N];
queue < pair < int, ll > > Service[N];

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, m, q, t, l, r, c, k;
    cin >> n >> m >> q;
    for(int i = 1; i <= q; ++ i) {
        cin >> t;
        Query[i] = 0;
        if(t == 1) {
            cin >> l >> r >> c >> k;
            Query[i] = -c;
            Time[l].push({i, k});
            Time[r + 1].push({i, -k});
        } else if(t == 2) {
            cin >> l >> r >> k;
            Time[l].push({i, -k});
            Time[r + 1].push({i, k});
        } else {
            cin >> c >> k;
            Service[c].push({i, k});
        }
    }
    for(int i = 1; i <= n; ++ i) {
        for(; !Time[i].empty(); Time[i].pop()) {
            update(Time[i].front().first, Time[i].front().second, 0, 0, N);     
            if(Query[Time[i].front().first]) {
                update(Time[i].front().first, Time[i].front().second);
            }
        }
        for(; !Service[i].empty(); Service[i].pop()) {
            ll ans = 0, cnt = get(Service[i].front().first);
            if(cnt >= Service[i].front().second) {
                cnt = Service[i].front().second + Sum(Service[i].front().first) - cnt;
                ans = -Query[find(cnt)];
            }
            Query[Service[i].front().first] = ans + 1;
        }
    }
    for(int i = 1; i <= q; ++ i) {
        if(Query[i] > 0) {
            cout << -- Query[i] << '\n';
        }
    }
}

Compilation message (stderr)

foodcourt.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main() {
      | ^~~~

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