Submission #1177112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177112		sleepntsheep	푸드 코트 (JOI21_foodcourt)	C++20	100 / 100	249 ms	39664 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;
	node(){ sum=pre=suf=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});
	    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].suf=t[p].pre=t[p].sum;
	t[p].pre=std::max(t[p].pre,0ll); t[p].suf=std::max(t[p].suf,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;
    }
    int lower_bound(long long val){
	long long sum=0,j,pos=0;
	for(j=1<<20;j/=2;)
	    if(pos+j<=n&&sum+t[pos+j-1]<val)sum+=t[(pos+=j)-1];
	return pos;
    }
} 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%lld", &qq[i].a, &qq[i].b, &qq[i].c, &qq[i].k);
	    ev[qq[i].a].push_back(i);
	    ev[qq[i].b+1].push_back(i);
	    fw.add(qq[i].a,qq[i].k);
	    fw.add(qq[i].b+1,-qq[i].k);
	} else if (qq[i].t == 2) {
	    scanf("%d%d%lld", &qq[i].a, &qq[i].b, &qq[i].k);
	    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?k:-k);
	    }else if(typ==2){
		st.upd(sec,b+1==i?k:-k);
	    }else{
		cur[sec]=st.qry(0,sec).suf;
	    }
	}
    }

    fw.init(q+5);
    for(int i=1;i<=n;++i){
	for(auto sec:ev[i]){
	    auto[typ,a,b,c,d,k]=qq[sec];
	    if(typ==1){
		fw.add(sec,a==i?k:-k);
	    }else{
		if(k<=cur[sec]){
		    long long y=tot[sec]-(cur[sec]-k);
		    fflush(stdout);
		    int sec2=fw.lower_bound(y);
		    qq[sec].d=qq[sec2].c;
		}
	    }
	}
    }

    for(int i=0;i<q;++i) if(qq[i].t==3) printf("%d\n",qq[i].d);

    return 0;
}

Compilation message (stderr)

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

• 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