Submission #1007093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007093		Unforgettablepl	Food Court (JOI21_foodcourt)	C++17	100 / 100	338 ms	45400 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

// #define x first
// #define y second

#define int long long

void solve1(int n,int m,int q){
    vector<deque<pair<int,int>>> queues(n+1);
    for(int i=1;i<=q;i++){
        int type;cin>>type;
        if(type==1){
            int l,r,c,k;cin>>l>>r>>c>>k;
            for(int x=l;x<=r;x++)queues[x].emplace_back(k,c);
        } else if(type==2){
            int l,r,k;cin>>l>>r>>k;
            for(int x=l;x<=r;x++){
                int tar = k;
                while(tar and !queues[x].empty()){
                    if(queues[x].front().first<=tar){
                        tar-=queues[x].front().first;
                        queues[x].pop_front();
                    } else {
                        queues[x].front().first-=tar;
                        tar = 0;
                    }
                }
            }
        } else {
            int a,b;cin>>a>>b;
            int curr = 0;
            for(int i=0;i<queues[a].size();i++){
                curr+=queues[a][i].first;
                if(curr>=b){cout<<queues[a][i].second<<'\n';break;}
            }
            if(curr<b)cout<<"0\n";
        }
    }
    exit(0);
}

pair<int,int> tree[2000000];

void merge(pair<int,int> &a,pair<int,int> b){
    int cut = min(a.second,b.first);
    a.second-=cut;
    b.first-=cut;
    a.first+=b.first;
    a.second+=b.second;
}
int n;

void update(int qL,int qR,pair<int,int> qu,int x=1,int l=1,int r=n){
    if(qR<l or r<qL)return;
    if(qL<=l and r<=qR){
        merge(tree[x],qu);
        return;
    }
    merge(tree[2*x],tree[x]);
    merge(tree[2*x+1],tree[x]);
    tree[x] = {0,0};
    int mid = (l+r)/2;
    update(qL,qR,qu,2*x,l,mid);
    update(qL,qR,qu,2*x+1,mid+1,r);
}

int get(int qu,int x=1,int l=1,int r=n){
    if(qu<l or r<qu)return 0;
    if(l==r){
        return tree[x].second;
    }
    merge(tree[2*x],tree[x]);
    merge(tree[2*x+1],tree[x]);
    tree[x] = {0,0};
    int mid = (l+r)/2;
    return get(qu,2*x,l,mid)+get(qu,2*x+1,mid+1,r);
}

void solve2(int n,int m,int q){
    for(int i=1;i<=q;i++){
        int type;cin>>type;
        if(type==1){
            int l,r,c,k;cin>>l>>r>>c>>k;
            update(l,r,{0,k});
        } else if(type==2){
            int l,r,k;cin>>l>>r>>k;
            update(l,r,{k,0});
        } else {
            int a,b;cin>>a>>b;
            if(get(a)<b)cout<<"0\n";
            else cout<<"1\n";
        }
    }
    exit(0);
}

struct fenwick{
    vector<int> tree;
    fenwick(int n):tree(n+1){}
    int get(int x){
        int ans = 0;
        while(x){
            ans+=tree[x];
            x-=x&-x;
        }
        return ans;
    }
    void update(int x,int k){
        while(x<tree.size()){
            tree[x]+=k;
            x+=x&-x;
        }
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,q;
    cin >> n >> m >> q;
    // if(n<=2000 and q<=2000)solve1(n,m,q);
    // if(m==1)solve2(n,m,q);
    
    fenwick addedamt(n);
    vector<vector<pair<int,int>>> queries(n+1);
    vector<vector<pair<int,bool>>> events(n+2);
    vector<pair<int,int>> addq(q+1);
    int out = 0;
    for(int i=1;i<=q;i++){
        int type;cin>>type;
        if(type==1){
            int l,r,c,k;cin>>l>>r>>c>>k;
            update(l,r,{0,k});
            addedamt.update(l,k);
            addedamt.update(r+1,-k);
            events[l].emplace_back(i,true);
            events[r+1].emplace_back(i,false);
            addq[i] = {c,k};
        } else if(type==2){
            int l,r,k;cin>>l>>r>>k;
            update(l,r,{k,0});
        } else {
            int a,b;cin>>a>>b;
            int act = b+addedamt.get(a)-get(a);
            if(act>addedamt.get(a))++out;
            else queries[a].emplace_back(act,++out);
        }
    }
    vector<int> ans(out+1);
    fenwick curr(q+1);
    for(int i=1;i<=n;i++){
        for(auto&[idx,type]:events[i]){
            if(type){
                curr.update(idx,addq[idx].second);
            } else {
                curr.update(idx,-addq[idx].second);
            }
        }
        for(auto&[act,idx]:queries[i]){
            int last = 0;
            for(int jump = 131072;jump;jump/=2){
                if(last+jump>q)continue;    
                if(curr.get(last+jump)<act)last+=jump;
            }
            last++;
            ans[idx] = addq[last].first;
        }
    }
    for(int i=1;i<=out;i++)cout<<ans[i]<<'\n';
}

Compilation message (stderr)

foodcourt.cpp: In function 'void solve1(long long int, long long int, long long int)':
foodcourt.cpp:33:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for(int i=0;i<queues[a].size();i++){
      |                         ~^~~~~~~~~~~~~~~~~
foodcourt.cpp: In member function 'void fenwick::update(long long int, long long int)':
foodcourt.cpp:110:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         while(x<tree.size()){
      |               ~^~~~~~~~~~~~

• 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