Submission #1117923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117923		Zero_OP	Food Court (JOI21_foodcourt)	C++14	100 / 100	365 ms	72816 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define dbg(x) "[" #x " = " << (x) << "]"

struct fenwick_tree{
    vector<long long> bit;
    fenwick_tree(int n) : bit(n + 1, 0) {}

    void update(int i, long long v){
        for(; i < (int)bit.size(); i += i & (-i)) bit[i] += v;
    }

    long long query(int i){
        long long sum = 0;
        for(; i > 0; i -= i & (-i)) sum += bit[i];
        return sum;
    }

    long long query(int l, int r){
        return query(r) - query(l - 1);
    }

    int find_last(long long target){
        int i = 0;
        for(int b = 17; b >= 0; --b){
            if(i + (1 << b) < (int)bit.size() && target - bit[i + (1 << b)] > 0){
                i += (1 << b);
                target -= bit[i];
            }
        }
        return i + 1;
    }
};

struct min_prefix_segment_tree{ //finding minimum prefix with maximum position
    vector<long long> lazy;
    vector<pair<long long, int>> st;

    min_prefix_segment_tree(int n ): st(n << 2), lazy(n << 2) {}

    void build(int id, int l, int r){
        if(l == r) st[id] = {0, -l};
        else{
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            st[id] = min(st[id << 1], st[id << 1 | 1]);
        }
    }

    void apply(int id, long long v){
        st[id].first += v;
        lazy[id] += v;
    }

    void lazy_down(int id){
        if(lazy[id] != 0){
            apply(id << 1, lazy[id]);
            apply(id << 1 | 1, lazy[id]);
            lazy[id] = 0;
        }
    }

    void update(int id, int l, int r, int u, int v, long long val){
        if(u <= l && r <= v) apply(id, val);
        else{
            int mid = l + r >> 1;
            lazy_down(id);
            if(u <= mid) update(id << 1, l, mid, u, v, val);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
            st[id] = min(st[id << 1], st[id << 1 | 1]);
        }
    }

    pair<long long, int> query(int id, int l, int r, int u, int v){
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        lazy_down(id);
        if(u > mid) return query(id << 1 | 1, mid + 1, r, u, v);
        if(mid >= v) return query(id << 1, l, mid, u, v);
        return min(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
    }
};

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, M, Q;
    cin >> N >> M >> Q;

    struct info_update{
        int type, c, k, id;
    };

    struct info_query{
        int id; long long b;
    };

    vector<vector<info_update>> updates(N);
    vector<vector<info_query>> queries(N);
    vector<int> color(Q + 1);

    for(int i = 1; i <= Q; ++i){
        int t;
        cin >> t;
        if(t == 1){
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            --l;
            updates[l].push_back({+1, c, k, i});
            if(r < N) updates[r].push_back({-1, c, k, i});
            color[i] = c;
        } else if(t == 2){
            int l, r, k;
            cin >> l >> r >> k;
            --l;
            updates[l].push_back({+2, -1, k, i});
            if(r < N) updates[r].push_back({-2, -1, k, i});
        } else if(t == 3){
            int a; long long b;
            cin >> a >> b;
            --a;
            queries[a].push_back({b, i});
        }
    }

    min_prefix_segment_tree tr(Q + 1);
    fenwick_tree ft(Q), f(Q), g(Q);

    tr.build(1, 0, Q);

    //ft : 1 and 2
    //f  : only 1
    //g  : only 2

    vector<int> answer(Q + 1, -1);

    for(int i = 0; i < N; ++i){
        for(auto [type, c, k, id] : updates[i]){
            if(abs(type) == 1){
                if(type < 0) tr.update(1, 0, Q, id, Q, -k), f.update(id, -k);
                if(type > 0) tr.update(1, 0, Q, id, Q, +k), f.update(id, +k);
            } else if(abs(type) == 2){
                if(type < 0) tr.update(1, 0, Q, id, Q, +k), g.update(id, -k);
                if(type > 0) tr.update(1, 0, Q, id, Q, -k), g.update(id, +k);
            } else assert(false);
        }

        for(auto [b, id] : queries[i]){
            long long minPrefix; int from;
            tie(minPrefix, from) = tr.query(1, 0, Q, 0, id);
            from = -from;

            long long f_sum = f.query(id);
            long long g_sum = g.query(id);
            long long prefixSum = f_sum - g_sum;
            long long cur = prefixSum - minPrefix;

            if(cur < b){
                answer[id] = 0;
            } else{
                long long loss = (g_sum - g.query(from)) + f.query(from) + b;
                answer[id] = color[f.find_last(loss)];
            }
        }
    }

    for(int i = 1; i <= Q; ++i){
        if(answer[i] != -1) cout << answer[i] << '\n';
    }

    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In constructor 'min_prefix_segment_tree::min_prefix_segment_tree(long long int)':
foodcourt.cpp:40:34: warning: 'min_prefix_segment_tree::st' will be initialized after [-Wreorder]
   40 |     vector<pair<long long, int>> st;
      |                                  ^~
foodcourt.cpp:39:23: warning:   'std::vector<long long int> min_prefix_segment_tree::lazy' [-Wreorder]
   39 |     vector<long long> lazy;
      |                       ^~~~
foodcourt.cpp:42:5: warning:   when initialized here [-Wreorder]
   42 |     min_prefix_segment_tree(int n ): st(n << 2), lazy(n << 2) {}
      |     ^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp: In member function 'void min_prefix_segment_tree::build(long long int, long long int, long long int)':
foodcourt.cpp:47:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             int mid = l + r >> 1;
      |                       ~~^~~
foodcourt.cpp: In member function 'void min_prefix_segment_tree::update(long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:70:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int mid = l + r >> 1;
      |                       ~~^~~
foodcourt.cpp: In member function 'std::pair<long long int, long long int> min_prefix_segment_tree::query(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:148:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |         for(auto [type, c, k, id] : updates[i]){
      |                  ^
foodcourt.cpp:158:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  158 |         for(auto [b, id] : queries[i]){
      |                  ^

• 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