제출 #475328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475328		nafis_shifat	Food Court (JOI21_foodcourt)	C++14	100 / 100	914 ms	68100 KiB

foodcourt

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
using namespace std;
const int mxn=3e5+5;
const int inf=1e9;

int n,m,q;


struct segtree {
    
    ll removed[4 * mxn] = {};
    ll added[4 * mxn] = {};
    pii tree[4 * mxn];

    void init(int n) {
        for(int i = 0; i < 4 * mxn; i++) tree[i] = {0,0};
    }

    pii merge(pii a, pii b) {
        return { b.f + max(0ll, a.f - b.s), a.s + max(0ll,b.s - a.f) };
    }


    void propogate(int node) {
        int left = node << 1;
        int right = left | 1;

        removed[left] += min(tree[node].f,tree[left].s);
        removed[right] += min(tree[node].f,tree[right].s);

        tree[left] = merge(tree[node], tree[left]);
        tree[right] = merge(tree[node], tree[right]);

        removed[left] += removed[node];
        removed[right] += removed[node];
        removed[node] = 0;

        

        added[left] += added[node];
        added[right] += added[node];
        added[node] = 0;

        tree[node] = {0,0};
    }

    void update(int node,int b,int e,int l,int r, pii v) {
        if(e < l || b > r) return;
        if(b >= l && e <= r) {

            removed[node] += min(v.first, tree[node].s);
            added[node] += v.s;
            tree[node] = merge(v, tree[node]);
            // cout<<"After update ("<<b<<" "<<e<<") ("<<v.f<<" - "<<v.s<<") ("<<tree[node].f<<" "<<tree[node].s<<") "<<removed[node]<<endl;
            return;
        }
        propogate(node);

        int mid = b + e >>1;
        int left = node << 1;
        int right = left | 1;

        update(left, b, mid, l, r, v);
        update(right, mid + 1, e, l, r, v);
    }

    int query(int node,int b,int e,int p) {
        if(b == e) return node;

        int mid = b + e >> 1;
        int left = node << 1;
        int right = left | 1;

        propogate(node);

        if(p <= mid) return query(left,b,mid,p);
        return query(right, mid + 1,e,p);
    }
} st;

int type[mxn],l[mxn],r[mxn],c[mxn];
ll k[mxn];

ll a[mxn],b[mxn];
int res[mxn];

ll pos[mxn];


int lo[mxn],hi[mxn];

struct BIT
{
    ll bit[mxn] = {};
    void init() {
        memset(bit,0,sizeof bit);
    }

    void update(int p,ll v) {
        if(p==0) return;
        for(;p < mxn; p += p & -p) bit[p] += v;
    }

    ll query(int p) {
        ll r = 0;
        for(;p > 0; p -= p & -p) r += bit[p];
        return r;
    }

    void add(int l,int r,ll x) {
        update(l,x);
        update(r + 1, - x);
    }
} bt;
int main() {
    memset(c, -1, sizeof c);
    memset(res,-1,sizeof res);
    cin >> n >> m >> q;
    st.init(n);


    for(int i = 1; i <= q; i++) {
        scanf("%d",&type[i]);

        if(type[i] == 1) {
            scanf("%d%d%d %lld",&l[i],&r[i],&c[i],&k[i]);
            st.update(1,1,n,l[i],r[i],{0,k[i]});
        } else if(type[i] == 2) {
            scanf("%d%d %lld",&l[i],&r[i],&k[i]);
            st.update(1,1,n,l[i],r[i],{k[i],0});

        } else {
            scanf("%lld %lld",&a[i],&b[i]);

            int node = st.query(1,1,n,a[i]);
            if(st.tree[node].s >= b[i]) {
                pos[i] = st.removed[node] + b[i];
            }
            else res[i] = 0;
        }
    }

    vector<int> mid[q + 1];

    for(int i = 1; i <= q; i++) {
        lo[i] = 1;
        hi[i] = q;
    }

    for(int x = 1; x <= 22; x++) {
        bt.init();
        for(int i = 1; i <= q; i++) mid[i].clear();

        for(int i = 1; i <= q; i++) {
            if(type[i] == 3 && res[i] != 0 && lo[i] <= hi[i]) {
                mid[(lo[i] + hi[i] >> 1)].push_back(i);
            }
        }

        for(int i = 1; i <= q; i++) {
            if(type[i] == 1) {
                bt.add(l[i],r[i],k[i]);
            }

            for(int p : mid[i]) {
                ll val = bt.query(a[p]);
                if(val >= pos[p]) {
                    res[p] = c[i];
                    hi[p] = i - 1;
                } else {
                    lo[p] = i + 1;
                }
            }
        }


    }

    for(int i = 1; i <= q; i++) {
        if(type[i] == 3) printf("%d\n",res[i]);
    }





    


}

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.cpp: In member function 'void segtree::update(int, int, int, int, int, std::pair<long long int, long long int>)':
foodcourt.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = b + e >>1;
      |                   ~~^~~
foodcourt.cpp: In member function 'int segtree::query(int, int, int, int)':
foodcourt.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = b + e >> 1;
      |                   ~~^~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:160:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |                 mid[(lo[i] + hi[i] >> 1)].push_back(i);
      |                      ~~~~~~^~~~~~~
foodcourt.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         scanf("%d",&type[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
foodcourt.cpp:130:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |             scanf("%d%d%d %lld",&l[i],&r[i],&c[i],&k[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:133:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |             scanf("%d%d %lld",&l[i],&r[i],&k[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:137:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |             scanf("%lld %lld",&a[i],&b[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