Submission #1176817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176817		sleepntsheep	Food Court (JOI21_foodcourt)	C++20	0 / 100	195 ms	31128 KiB

foodcourt

#include <vector>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>
#include <stdio.h>

using namespace std;
template<typename T>
using ve=std::vector<T>;
using pii=std::pair<int,int>;

int n, m, q, sub3, sub4;
struct Q{
    int t,a,b,c,d;
    long long k;
}qq[250000];

int main() {
    scanf("%d%d%d", &n, &m, &q);

    sub3 = 1;
    sub4 = m == 1;

    sub4=1;
    for (int i = 0; i < q; ++i) {
	scanf("%d", &qq[i].t);
	if (qq[i].t == 1) {
	    scanf("%d%d%d%d", &qq[i].a, &qq[i].b, &qq[i].c, &qq[i].d);
	    sub3 &= (qq[i].b - qq[i].a <= 10 && qq[i].d == 1);
	}
	else if (qq[i].t == 2)
	    scanf("%d%d%d", &qq[i].a, &qq[i].b, &qq[i].c);
	else
	    scanf("%d%lld", &qq[i].a, &qq[i].k);
    }

    if(0&&n<=2000&&q<=2000){
	ve<deque<pii>>x(2001);
	for(int i=0;i<q;++i){
	    auto[t,a,b,c,d,k]=qq[i];
	    if(t==1){
		for(int j=a;j<=b;++j)x[j].emplace_back(d,c);
	    }else if(t==2){
		for(int j=a;j<=b;++j){
		    int k2=c;
		    while(x[j].size()&&k2){
			if(x[j][0].first<=k2){
			    k2-=x[j][0].first;
			    x[j].pop_front();
			}else{
			    x[j][0].first-=k2;
			    k2=0;
			}
		    }
		}
	    }else{
		long long j=0,k2=k;
		for(;j<=x[a].size()&&k2;++j){
		    if(j==x[a].size()){
			puts("0");
			break;
		    } else if(k2<=x[a][j].first){
			printf("%d\n",x[a][j].second);
			k2=0;
			break;
		    }else{
			k2-=x[a][j].first;
		    }
		}
	    }
	}
    }
    else if(0&&sub3){
	set<int>s;
	ve<deque<int>>x(n+1);
	for(int i=0;i<q;++i){
	    auto[t,a,b,c,d,k]=qq[i];
	    if(t==1){
		for(int j=a;j<=b;++j){
		    if(x[j].empty())s.insert(j);
		    x[j].push_back(c);
		}
	    }else if(t==2){
		auto it=s.lower_bound(a);
		for(;it!=s.end()&&*it<=b;){
		    int k2=c;
		    while(x[*it].size()&&k2--){
			x[*it].pop_front();
		    }
		    if(x[*it].empty())it=s.erase(it);
		    else ++it;
		}
	    }else{
		if(k<=x[a].size())printf("%d\n",x[a][k-1]);
		else puts("0");
	    }
	}
    } else if (sub4){
	struct{
	    int sent=0;
	    ve<long long>tt,lza,lzb;

	    void x(){
		tt.assign(999999,0);
		lza.assign(999999,sent);
		lzb.assign(999999,0);
	    }

	    void pus(int v,int l,int r){
		if(lzb[v]){
		    if(l!=r){
			lzb[v*2+1]=lzb[v];
			lzb[v*2+2]=lzb[v];
		    }else{
			tt[v]=std::max(tt[v],0ll);
		    }
		    lzb[v]=0;
		}
		if(lza[v]-sent){
		    if(l!=r){
			lza[v*2+1]+=lza[v];
			lza[v*2+2]+=lza[v];
		    }else{
			tt[v]+=lza[v];
		    }
		    lza[v]=sent;
		}
	    }
	    void add(int v,int l,int r,int x,int y,int k){
		pus(v,l,r);
		if(r<x||y<l)return;
		if(x<=l&&r<=y){
		    lza[v]=k;
		    pus(v,l,r);
		    return;
		}
		add(v*2+1,l,(l+r)/2,x,y,k);
		add(v*2+2,(l+r)/2+1,r,x,y,k);
	    }
	    void chmax(int v,int l,int r,int x,int y){
		pus(v,l,r);
		if(r<x||y<l)return;
		if(x<=l&&r<=y){
		    lzb[v]=1;
		    pus(v,l,r);
		    return;
		}
		chmax(v*2+1,l,(l+r)/2,x,y);
		chmax(v*2+2,(l+r)/2+1,r,x,y);
	    }
	    long long pt(int v,int l,int r,int p){
		pus(v,l,r);
		if(l==r)return tt[v];
		if(p<=(l+r)/2)return pt(v*2+1,l,(l+r)/2,p);
		else return pt(v*2+2,(l+r)/2+1,r,p);
	    }
	}s;
	s.x();

	for(int i=0;i<q;++i){
	    auto[t,a,b,c,d,k]=qq[i];
	    if(t==1){
		s.add(0,0,n,a,b,c);
	    }else if(t==2){
		s.add(0,0,n,a,b,-c);
		s.chmax(0,0,n,a,b);
	    }else{
		long long k2=s.pt(0,0,n,a);
		printf("%d\n",k2>=k?1:0);
	    }
	}

    }



    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d%d%d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d", &qq[i].t);
      |         ~~~~~^~~~~~~~~~~~~~~~
foodcourt.cpp:29:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |             scanf("%d%d%d%d", &qq[i].a, &qq[i].b, &qq[i].c, &qq[i].d);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             scanf("%d%d%d", &qq[i].a, &qq[i].b, &qq[i].c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |             scanf("%d%lld", &qq[i].a, &qq[i].k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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