Submission #1003355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003355		79brue	Food Court (JOI21_foodcourt)	C++17	68 / 100	348 ms	29440 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct segTree1{
    ll treeMax[1<<19], treeMin[1<<19], lazyA[1<<19], lazyB[1<<19];

    void init(int i, int l, int r){
        treeMax[i] = treeMin[i] = 0;
        lazyA[i] = 1, lazyB[i] = 0;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void propagate(int i, int l, int r){
        treeMax[i] = treeMax[i] * lazyA[i] + lazyB[i];
        treeMin[i] = treeMin[i] * lazyA[i] + lazyB[i];
        if(l!=r){
            lazyB[i*2] = lazyB[i*2] * lazyA[i] + lazyB[i], lazyA[i*2] *= lazyA[i];
            lazyB[i*2+1] = lazyB[i*2+1] * lazyA[i] + lazyB[i], lazyA[i*2+1] *= lazyA[i];
        }
        lazyA[i] = 1, lazyB[i] = 0;
    }

    void update(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            if(v>=0 || treeMin[i]+v >= 0){
                lazyB[i] += v;
                propagate(i, l, r);
                return;
            }
            if(treeMax[i]+v <= 0){
                lazyA[i] = 0, lazyB[i] = 0;
                propagate(i, l, r);
                return;
            }
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        treeMax[i] = max(treeMax[i*2], treeMax[i*2+1]);
        treeMin[i] = min(treeMin[i*2], treeMin[i*2+1]);
    }

    ll query(int i, int l, int r, int x){
        propagate(i, l, r);
        if(l==r) return treeMax[i];
        int m = (l+r)>>1;
        if(x<=m) return query(i*2, l, m, x);
        else return query(i*2+1, m+1, r, x);
    }
} tree1;

struct segTree2{
    int n;
    ll tree[250002];

    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++) tree[i] = 0;
    }

    void add(int x, ll v){
        while(x<=n){
            tree[x] += v;
            x += x&-x;
        }
    }

    ll sum(int x){
        ll ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }
} tree2;

struct dat{
    int x, idx; ll v;
    dat(){}
    dat(int x, int idx, ll v): x(x), idx(idx), v(v){}
    bool operator<(const dat &r)const{
        return x<r.x;
    }
};

int records[250002]; int rcnt;
struct segTree3{
    ll tree[1<<19], lazy[1<<19];

    void init(int i, int l, int r, dat *arr){
        if(l==r){
            tree[i] = arr[l].v;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, arr);
        init(i*2+1, m+1, r, arr);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    void propagate(int i, int l, int r){
        tree[i] += lazy[i];
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    void search_range(int i, int l, int r){
        propagate(i, l, r);
        if(tree[i] > 0) return;
        if(l==r){
            records[++rcnt] = l;
            tree[i] = INF;
            return;
        }
        int m = (l+r)>>1;
        search_range(i*2, l, m);
        search_range(i*2+1, m+1, r);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    void update(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] -= v;
            search_range(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }
} tree3;

int n, m, q;
int qt[250002], ql[250002], qr[250002], qx[250002];
ll qk[250002], qb[250002];
int ans[250002];

int s;
dat queries[250002];
int qli[250002];

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=q; i++){
        scanf("%d", &qt[i]);
        if(qt[i] == 1) scanf("%d %d %d %lld", &ql[i], &qr[i], &qx[i], &qk[i]);
        else if(qt[i] == 2) scanf("%d %d %lld", &ql[i], &qr[i], &qk[i]);
        else scanf("%d %lld", &qx[i], &qk[i]);
    }

    tree1.init(1, 1, n);
    tree2.init(n);
    for(int i=1; i<=q; i++){
        if(qt[i] == 1){
            if(n<=65000) tree1.update(1, 1, n, ql[i], qr[i], qk[i]);
            tree2.add(ql[i], qk[i]);
            tree2.add(qr[i]+1, -qk[i]);
        }
        else if(qt[i] == 2){
            if(n<=65000) tree1.update(1, 1, n, ql[i], qr[i], -qk[i]);
        }
        else{
            ll a = tree2.sum(qx[i]), b = tree1.query(1, 1, n, qx[i]);
            if(b < qk[i]) continue;
            queries[++s] = dat(qx[i], i, a - b + qk[i]);
        }
    }

    if(s){
        sort(queries+1, queries+s+1);
        queries[s+1].x = INT_MAX;
        for(int i=1; i<=n+1; i++){
            qli[i] = qli[i-1];
            while(queries[qli[i]].x < i) qli[i]++;
        }
        tree3.init(1, 1, s, queries);

        for(int i=1; i<=q; i++){
            if(qt[i] != 1) continue;
            tree3.update(1, 1, s, qli[ql[i]], qli[qr[i]+1]-1, qk[i]);
            for(int p=1; p<=rcnt; p++){
                ans[queries[records[p]].idx] = qx[i];
            }
            rcnt = 0;
        }
    }

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

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         scanf("%d", &qt[i]);
      |         ~~~~~^~~~~~~~~~~~~~
foodcourt.cpp:159:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         if(qt[i] == 1) scanf("%d %d %d %lld", &ql[i], &qr[i], &qx[i], &qk[i]);
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:160:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         else if(qt[i] == 2) scanf("%d %d %lld", &ql[i], &qr[i], &qk[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:161:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         else scanf("%d %lld", &qx[i], &qk[i]);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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