Submission #878354

#	Time	Username	Problem	Language	Result	Execution time	Memory
878354		prohacker	Food Court (JOI21_foodcourt)	C++14	100 / 100	382 ms	64988 KiB

foodcourt

#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const int N = 250010;
const int INF = INT_MAX;
const int mod = 1e9+7;
const string NAME = "solve";

int n,m,q;
vector<pair<int,ll>> adj[N],events_bit[N],events_seg[N];
int ans[N];
int gr[N];

struct Fenwick{
    ll bit[N];

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

    ll get(int idx) {
        ll res = 0;
        for(; idx > 0; idx -= (idx & (-idx))) {
            res += bit[idx];
        }
        return res;
    }

    int walk(ll val) {
        int res = 0;
        for(int i = 18 ; i >= 0 ; i--) {
            if(res+(1<<i) < N and bit[res+(1<<i)] < val) {
                val -= bit[res+(1<<i)];
                res += (1<<i);
            }
        }
        return res+1;
    }

}bit;

struct Segment{
    struct Node{
        ll cur = 0;
        ll sum = 0;
        Node() {};
        Node(ll _cur, ll _sum) { cur = _cur; sum = _sum; };
        Node operator + (const Node& other) {
            return Node(max(this -> cur+other.sum,other.cur),this -> sum+other.sum);
        }
    }tree[4*N];

    void update(int pos, ll val, int id = 1, int l = 1, int r = N-10) {
        if(l == r) {
            tree[id] = Node(max(0LL,val),val);
            return;
        }
        int mid = l + r >> 1;
        if(pos <= mid) {
            update(pos,val,id << 1,l,mid);
        }
        else {
            update(pos,val,id << 1 | 1,mid+1,r);
        }
        tree[id] = tree[id << 1] + tree[id << 1 | 1];
    }

    Node get(int u, int v, int id = 1, int l = 1, int r = N-10) {
        if(r < u or v < l) {
            return Node(0,0);
        }
        if(u <= l and r <= v) {
            return tree[id];
        }
        int mid = l + r >> 1;
        return get(u,v,id << 1,l,mid) + get(u,v,id << 1 | 1,mid+1,r);
    }

}tree;

signed main()
{
    if (fopen((NAME + ".inp").c_str(), "r")) {
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1 ; i <= q ; i++) {
        int type; cin >> type;
        if(type == 1) {
            int l,r,c;
            ll k; cin >> l >> r >> c >> k;
            events_seg[l].push_back({i,k});
            events_bit[l].push_back({i,k});
            events_seg[r+1].push_back({i,0});
            events_bit[r+1].push_back({i,-k});
            gr[i] = c;
        }
        else if(type == 2) {
            int l,r;
            ll k; cin >> l >> r >> k;
            events_seg[l].push_back({i,-k});
            events_seg[r+1].push_back({i,0});
        }
        else {
            int a;
            ll b; cin >> a >> b;
            adj[a].push_back({i,b});
        }
    }
    for(int i = 1 ; i <= q ; i++) {
        ans[i] = -1;
    }
    for(int i = 1 ; i <= n ; i++) {
        for(auto p:events_seg[i]) {
            tree.update(p.first,p.second);
        }
        for(auto p:events_bit[i]) {
            bit.update(p.first,p.second);
        }
        for(auto p:adj[i]) {
            auto s = tree.get(1,p.first);
            if(p.second <= s.cur) {
                ll Real = bit.get(p.first) - (s.cur - p.second);
                ans[p.first] = gr[bit.walk(Real)];
            }
            else {
                ans[p.first] = 0;
            }
        }
    }
    for(int i = 1 ; i <= q ; i++) {
        if(ans[i] != -1) {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void Segment::update(int, long long int, int, int, int)':
foodcourt.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'Segment::Node Segment::get(int, int, int, int, 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:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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