Submission #878635

#	Time	Username	Problem	Language	Result	Execution time	Memory
878635		thangdz2k7	Food Court (JOI21_foodcourt)	C++17	100 / 100	441 ms	62804 KiB

foodcourt

#include <bits/stdc++.h>
#define ll pair <long long, long long>
#define ii pair <int, long long>
#define F first
#define S second
#define pb push_back
#define ill long long

using namespace std;

const int N = 2e5 + 5e4 + 5;

int n, m, q, group[N], ans[N];
vector <ii> event[N], numadd[N], query[N];

long long cur[4 * N], Min[4 * N];

void update_cur(int s, int l, int r, int u, ill val){
    if (l == r){
        cur[s] += val;
        Min[s] = min(0ll, cur[s]);
        return;
    }

    int mid = l + r >> 1;
    if (mid >= u) update_cur(2 * s, l, mid, u, val);
    else update_cur(2 * s + 1, mid + 1, r, u, val);

    cur[s] = cur[2 * s] + cur[2 * s + 1];
    Min[s] = min(Min[2 * s], cur[2 * s] + Min[2 * s + 1]);
}

ll get_cur(int s, int l, int r, int u){
    if (l > u) return ll(0, 0);
    if (r <= u) return ll(cur[s], Min[s]);

    int mid = l + r >> 1;
    ll A = get_cur(2 * s, l, mid, u);
    ll B = get_cur(2 * s + 1, mid + 1, r, u);

    return ll(A.F + B.F, min(A.S, A.F + B.S));
}

long long sumadd[4 * N];

void update_sumadd(int s, int l, int r, int u, ill val){
    if (l == r){
        sumadd[s] += val;
        return;
    }

    int mid = l + r >> 1;
    if (mid >= u) update_sumadd(2 * s, l, mid, u, val);
    else update_sumadd(2 * s + 1, mid + 1, r, u, val);
    sumadd[s] = sumadd[2 * s] + sumadd[2 * s + 1];
}

long long get_sumadd(int s, int l, int r, int u){
    if (l > u) return 0;
    if (r <= u) return sumadd[s];

    int mid = l + r >> 1;
    return get_sumadd(2 * s, l, mid, u) + get_sumadd(2 * s + 1, mid + 1, r, u);
}

int get_pos(int s, int l, int r, long long val){
    if (l == r) return l;
    int mid = l + r >> 1;
    if (sumadd[2 * s] < val) return get_pos(2 * s + 1, mid + 1, r, val - sumadd[2 * s]);
    return get_pos(2 * s, l, mid, val);
}

void solve(){
    cin >> n >> m >> q;
    for (int i = 1; i <= q; ++ i){
        ans[i] = -1;
        int t; cin >> t;
        if (t == 1){
            int l, r, k; cin >> l >> r >> group[i] >> k;
            event[l].pb(ii(i, k));
            event[r + 1].pb(ii(i, -k));
            numadd[l].pb(ii(i, k));
            numadd[r + 1].pb(ii(i, -k));
        }
        if (t == 2){
            int l, r, k; cin >> l >> r >> k;
            event[l].pb(ii(i, -k));
            event[r + 1].pb(ii(i, k));
        }
        if (t == 3){
            int a;
            ill b; cin >> a >> b;
            query[a].pb(ii(i, b));
        }
    }

    for (int i = 1; i <= n; ++ i){
        for (ii v : event[i]) {
            update_cur(1, 1, q, v.F, v.S);
            //cout << i << ' ' << v.F << ' ' << v.S << endl;
        }
        for (ii v : numadd[i]) update_sumadd(1, 1, q, v.F, v.S);
        for (ii v : query[i]){
            ll gnum_cur = get_cur(1, 1, q, v.F);
            long long num_cur = gnum_cur.F - gnum_cur.S;
            //cout << gnum_cur.F << ' ' << gnum_cur.S << endl;
            long long num_add = get_sumadd(1, 1, q, v.F);
            if (num_cur < v.S) ans[v.F] = 0;
            else ans[v.F] = group[get_pos(1, 1, q, num_add - num_cur + v.S)];
        }
    }

    for (int i = 1; i <= q; ++ i) if (ans[i] >= 0) cout << ans[i] << '\n';
}

signed main(){
    //freopen("foodcourt.inp", "r", stdin);
    //freopen("foodcourt.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'void update_cur(int, int, int, int, long long int)':
foodcourt.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In function 'std::pair<long long int, long long int> get_cur(int, int, int, int)':
foodcourt.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In function 'void update_sumadd(int, int, int, int, long long int)':
foodcourt.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In function 'long long int get_sumadd(int, int, int, int)':
foodcourt.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In function 'int get_pos(int, int, int, long long int)':
foodcourt.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int mid = l + r >> 1;
      |               ~~^~~

• 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