Submission #1177088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177088		sleepntsheep	Food Court (JOI21_foodcourt)	C++20	0 / 100	164 ms	38440 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;
struct Q{
    int t,a,b,c,d;
    long long k;
};

struct S{
    struct node{
	long long sum,pre,suf,ans;
	node(){ sum=pre=suf=ans=0; }
	friend node operator+(const node&a,const node&b){
	    node c;
	    c.sum=a.sum+b.sum;
	    c.pre=std::max({a.pre,a.sum+b.pre});
	    c.suf=std::max({b.suf,b.sum+a.suf});
	    c.ans=std::max({a.ans,b.ans,a.suf+b.pre});
	    return c;
	}
    };
    ve<node>t;
    S(){}
    ~S(){}
    int n;
    void init(int n0){
	n=n0;t.assign(n*2,node());
    }
    void pul(int p){
	t[p]=t[p*2]+t[p*2+1];
    }
    void upd(int p,long long k){
	p+=n;
	t[p].sum+=k;
	t[p].pre+=k;
	t[p].suf+=k;
	t[p].ans+=k;
	t[p].pre=std::max(t[p].pre,0ll); t[p].suf=std::max(t[p].suf,0ll); t[p].ans=std::max(t[p].ans,0ll);
	for(;p/=2;)pul(p);
    }
    node qry(int l,int r){
	node zl,zr;
	for(l+=n,r+=n+1;l<r;l/=2,r/=2){
	    if(l&1)zl=zl+t[l++];
	    if(r&1)zr=t[--r]+zr;
	}
	return zl+zr;
    }
} st;

struct F{
    ve<long long>t;
    int n;
    F(){}
    ~F(){}
    void init(int n0){
	t.assign(n=n0,0);
    }
    void add(int p,long long k){
	for(;p<n;p|=p+1)t[p]+=k;
    }
    long long sum(int p){
	long long z=0;
	for(;p;p&=p-1)z+=t[p-1];
	return z;
    }
} fw;

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

    ve<Q>qq(q);
    ve<ve<int>>ev(n+5);
    ve<long long>cur(q),tot(q);
    st.init(q+5);
    fw.init(n+5);

    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);
	    ev[qq[i].a].push_back(i);
	    ev[qq[i].b+1].push_back(i);
	    fw.add(qq[i].a,qq[i].d);
	    fw.add(qq[i].b+1,-qq[i].d);
	} else if (qq[i].t == 2) {
	    scanf("%d%d%d", &qq[i].a, &qq[i].b, &qq[i].c);
	    ev[qq[i].a].push_back(i);
	    ev[qq[i].b+1].push_back(i);
	} else {
	    scanf("%d%lld", &qq[i].a, &qq[i].k);
	    ev[qq[i].a].push_back(i);
	    tot[i]=fw.sum(qq[i].a+1);
	}
    }

    for(int i=1;i<=n;++i){
	for(auto sec:ev[i]){
	    auto[typ,a,b,c,d,k]=qq[sec];
	    if(typ==1){
		st.upd(sec,a==i?d:-d);
	    }else if(typ==2){
		st.upd(sec,b+1==i?d:-d);
	    }else{
		auto x=st.qry(0,sec);
		cur[sec]=x.ans;
	    }
	}
    }

    for(int i=0;i<q;++i){
	auto[typ,a,b,c,d,k]=qq[i];
	if(typ==3){
	    if(cur[i]>=k)puts("1");
	    else puts("0");
	}
    }

    return 0;
}

Compilation message (stderr)

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