Submission #1176802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176802		sleepntsheep	Food Court (JOI21_foodcourt)	C++20	7 / 100	69 ms	46152 KiB

foodcourt

#include <vector>
#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;
struct Q{
    int t,a,b,c,d;
    long long k;
}qq[250000];

int main() {
    sub3 = 1;

    scanf("%d%d%d", &n, &m, &q);
    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(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(sub3){
	set<int>s;
	ve<deque<int>>x(n);
	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");
	    }
	}
    }



    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d%d%d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d", &qq[i].t);
      |         ~~~~~^~~~~~~~~~~~~~~~
foodcourt.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |             scanf("%d%d%d%d", &qq[i].a, &qq[i].b, &qq[i].c, &qq[i].d);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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", &qq[i].a, &qq[i].b, &qq[i].c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |             scanf("%d%lld", &qq[i].a, &qq[i].k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 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