Submission #388714

#	Time	Username	Problem	Language	Result	Execution time	Memory
388714		georgerapeanu	Food Court (JOI21_foodcourt)	C++11	0 / 100	849 ms	208440 KiB

foodcourt

#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>

using namespace std;

class SegmentTree{
    struct node_t{
        long long a,b;///LEAVE a, JOIN b

        node_t operator + (const node_t &other)const{
            node_t ans;
            ans = *this;
            ans.b -= other.a;
            if(ans.b < 0){
                ans.a -= ans.b;
                ans.b = 0;
            }
            ans.b += other.b;
            return ans;
        }

        node_t(){
            a = b = 0;
        }

        node_t(long long a,long long b){
            this->a = a;
            this->b = b;
        }
    };

    int n;
    vector<node_t> aint;

    void propagate(int nod,int st,int dr){
        if(st == dr){
            return ;
        }

        aint[nod * 2] = aint[nod * 2] + aint[nod];
        aint[nod * 2 + 1] = aint[nod * 2 + 1] + aint[nod];
        aint[nod] = node_t();
    }
    
    void update(int nod,int st,int dr,int l,int r,node_t val){
        propagate(nod,st,dr);

        if(dr < l || st > r){
            return ;
        }

        if(l <= st && dr <= r){
            aint[nod] = aint[nod] + val;
            return ;
        }

        int mid = (st + dr) / 2;

        update(nod * 2,st,mid,l,r,val);
        update(nod * 2 + 1,mid + 1,dr,l,r,val);
    }

    node_t access(int nod,int st,int dr,int pos){
        propagate(nod,st,dr);
        if(dr < pos || st > pos){
            return node_t();
        }
        if(st == dr){
            return aint[nod];
        }

        int mid = (st + dr) / 2;

        return access(nod * 2,st,mid,pos) + access(nod * 2 + 1,mid + 1,dr,pos);
    }

public:

    SegmentTree(int n){
        this->n = n;
        this->aint = vector<node_t>(4 * n + 5);
    }

    void add(int l,int r,long long value){
        update(1,1,n,l,r,{0,value});
    }

    void remove(int l,int r,long long value){
        update(1,1,n,l,r,{value,0});
    }

    long long access(int pos){
        return access(1,1,n,pos).b;
    }
};

class FenwickTree{
    int n;
    vector<long long> aib;

    void update(int pos,long long value){
        for(;pos <= n;pos += (-pos) & pos){
            aib[pos] += value;
        }
    }

    long long query(int pos){
        long long ans = 0;

        for(;pos;pos -= (-pos) & pos){
            ans += aib[pos];
        }

        return ans;
    }

public:
 
    FenwickTree(int n){
        this->n = n;
        this->aib = vector<long long>(n + 1);
    }

    void add(int l,int r,long long value){
        update(l,value);
        update(r + 1,-value);
    }

    long long access(int pos){
        return query(pos);
    }
};

class SegmentTree2{///cause why not
    int n;
    vector<pair<long long,int> > aint;
    vector<long long> lazy;

    void propagate(int nod,int st,int dr){
        if(lazy[nod] == 0 || st == dr){
            return ;
        }

        lazy[nod * 2] += lazy[nod];
        lazy[nod * 2 + 1] += lazy[nod];
        aint[nod * 2].first -= lazy[nod];
        aint[nod * 2 + 1].first -= lazy[nod];
        lazy[nod] = 0;
    }

    void build(int nod,int st,int dr){
        if(st == dr){
            aint[nod] = {0,st};
            return ;
        }

        int mid = (st + dr) / 2;

        build(nod * 2,st,mid);
        build(nod * 2 + 1,mid + 1,dr);

        aint[nod] = min(aint[nod * 2],aint[nod * 2 + 1]);
    }

    void update_range(int nod,int st,int dr,int l,int r,long long value){
        propagate(nod,st,dr);

        if(r < st || l > dr){
            return ;
        }

        if(l <= st && dr <= r){
            aint[nod].first -= value;
            lazy[nod] += value;
            return ;
        }

        int mid = (st + dr) / 2;

        update_range(nod * 2,st,mid,l,r,value);
        update_range(nod * 2 + 1,mid + 1,dr,l,r,value);

        aint[nod] = min(aint[nod * 2],aint[nod * 2 + 1]);
    }

    void update_set(int nod,int st,int dr,int pos,long long value){
        propagate(nod,st,dr);

        if(dr < pos || st > pos){
            return ;
        }

        if(st == dr){
            aint[nod].first = value;
            return ;
        }

        int mid = (st + dr) / 2;

        update_set(nod * 2,st,mid,pos,value);
        update_set(nod * 2 + 1,mid + 1,dr,pos,value);

        aint[nod] = min(aint[nod * 2],aint[nod * 2 + 1]);
    }

public:

    SegmentTree2(int n){
        this->n = n;
        aint = vector<pair<long long,int> >(4 * n + 5);
        lazy = vector<long long>(4 * n + 5);
        build(1,1,n);
    }

    void update_range(int l,int r,long long value){
        update_range(1,1,n,l,r,value);
    }

    void update_set(int pos,long long value){
        update_set(1,1,n,pos,value);
    }

    pair<long long,int> query(){
        return aint[1];
    }
};

const int NMAX = 250000;
const int MMAX = 250000;
const int QMAX = 250000;

int n,m,q;

struct query_t{
    int l,r,c;
    long long k;    
};

deque<pair<long long,int> > queries[NMAX + 5];
int answer[QMAX + 5];

int main(){

    scanf("%d %d %d",&n,&m,&q);
    
    vector<query_t> query_list;

    SegmentTree aint(n);
    FenwickTree aib(n);

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

        if(t == 1){
            int l,r,c;
            long long k;
            scanf("%d %d %d %lld",&l,&r,&c,&k);
            aint.add(l,r,k);
            aib.add(l,r,k);
            query_list.push_back({l,r,c,k});
        }else if(t == 2){
            int l,r;
            long long k;
            scanf("%d %d %lld",&l,&r,&k);
            aint.remove(l,r,k);
        }else{
            int a;
            long long b;
            scanf("%d %lld",&a,&b);
            long long total = aib.access(a);
            long long cnt = aint.access(a);

            if(cnt >= b){
                queries[a].push_back({total - cnt + b,i});
            }else{
                answer[i] = -1;
            }
        }
    }

    SegmentTree2 aint2(n);

    for(int i = 1;i <= n;i++){
        sort(queries[i].begin(),queries[i].end());
        if(queries[i].empty()){
            aint2.update_set(i,1e18);
        }else{
            aint2.update_set(i,queries[i].front().first);
        }
    }
    
    for(auto it:query_list){
        aint2.update_range(it.l,it.r,it.k);
        while(aint2.query().first <= 0){
            int pos = aint2.query().second;
            answer[queries[pos].front().second] = it.c;
            queries[pos].pop_front();
            if(queries[pos].empty()){
                aint2.update_set(pos,1e18);
            }else{
                aint2.update_range(pos,pos,-queries[pos].front().first);///Ugly? yes. does it work? i hope so
            }
        }
    }

    for(int i = 1;i <= q;i++){
        if(answer[i] != 0){
            printf("%d\n",(answer[i] == -1 ? 0:answer[i]));
        }
    }

    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:246:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  246 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:255:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  255 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
foodcourt.cpp:260:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  260 |             scanf("%d %d %d %lld",&l,&r,&c,&k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:267:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  267 |             scanf("%d %d %lld",&l,&r,&k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:272:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  272 |             scanf("%d %lld",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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