oj.uz

답안 #439007

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
439007 2021-06-29T04:05:44 Z kig9981 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 1000 ms 74856 KB 
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct Seg
{
	long long mn, smn, lz, slz;
	Seg() : mn(0), smn(0x7fffffffffffffffLL), lz(0), slz(-0x7fffffffffffffffLL) {}
	Seg &operator =(const Seg &a) {
		mn=a.mn;
		smn=a.smn;
		return *this;
	}
};

const int SZ=1<<18;
const long long MAX=0x7fffffffffffffffLL;
Seg tree[2*SZ];
vector<tuple<int,int,long long>> L[2*SZ];

void update(int s, int e, int q, int c, int k)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) {
			L[s].emplace_back(q,c,get<2>(L[s].back())+k);
			s++;
		}
		if(~e&1) {
			L[e].emplace_back(q,c,get<2>(L[e].back())+k);
			e--;
		}
	}
}

Seg combine(const Seg &a, const Seg &b)
{
	Seg c;
	c.mn=min(a.mn,b.mn);
	if(c.mn<max(a.mn,b.mn)) c.smn=max(a.mn,b.mn);
	if(c.mn<a.smn) c.smn=max(c.smn,a.smn);
	if(c.mn<b.smn) c.smn=max(c.smn,b.smn);
	return c;

}

void lazy_propagation(int bit, int s, int e)
{
	if(tree[bit].slz!=-MAX) {
		if(s<e) {
			if(max(tree[2*bit].slz,tree[2*bit].mn)+tree[2*bit].lz==tree[bit].mn) tree[2*bit].slz=tree[bit].slz-tree[2*bit].lz;
			if(max(tree[2*bit+1].slz,tree[2*bit+1].mn)+tree[2*bit+1].lz==tree[bit].mn) tree[2*bit+1].slz=tree[bit].slz-tree[2*bit+1].lz;
		}
		tree[bit].mn=tree[bit].slz;
		tree[bit].slz=-MAX;
	}
	tree[bit].mn+=tree[bit].lz;
	if(tree[bit].smn<MAX) tree[bit].smn+=tree[bit].lz;
	if(s<e) {
		tree[2*bit].lz+=tree[bit].lz;
		tree[2*bit+1].lz+=tree[bit].lz;
	}
	tree[bit].lz=0;
}

void add_tree(int n1, int n2, int v, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		tree[bit].lz=v;
		lazy_propagation(bit,s,e);
		return;
	}
	add_tree(n1,n2,v,2*bit,s,m);
	add_tree(n1,n2,v,2*bit+1,m+1,e);
	tree[bit]=combine(tree[2*bit],tree[2*bit+1]);
}

void set_tree(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1 || tree[bit].mn>=0) return;
	if(n1<=s && e<=n2 && tree[bit].smn>0) {
		tree[bit].slz=0;
		lazy_propagation(bit,s,e);
		return;
	}
	set_tree(n1,n2,2*bit,s,m);
	set_tree(n1,n2,2*bit+1,m+1,e);
	tree[bit]=combine(tree[2*bit],tree[2*bit+1]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, Q;
	cin>>N>>M>>Q;
	for(int i=2*SZ;--i;) L[i].emplace_back(0,0,0);
	for(int i=1;i<=Q;i++) {
		int t, a, c, d;
		long long b;
		cin>>t>>a>>b;
		if(t==1) {
			cin>>c>>d;
			update(--a,--b,i,c,d);
			add_tree(a,b,d);
		}
		else if(t==2) {
			cin>>c;
			add_tree(--a,--b,-c);
			set_tree(a,b);
		}
		else {
			long long tot;
			int n=1, s=0, e=SZ-1; --a;
			while(s<e) {
				int m=(s+e)>>1;
				lazy_propagation(n,s,e);
				if(a<=m) tie(n,e)=make_pair(2*n,m);
				else tie(n,s)=make_pair(2*n+1,m+1);
			}
			lazy_propagation(n,s,e);
			if(tree[n].mn<b) {
				cout<<"0\n";
				continue;
			}
			for(tot=get<2>(L[n=SZ+a].back());n>>=1;) tot+=get<2>(L[n].back());
			b+=tot-tree[SZ+a].mn;
			s=1; e=i-1;
			while(s<=e) {
				int m=(s+e)>>1; tot=0; n=SZ+a;
				for(;;) {
					tot+=get<2>(*--upper_bound(L[n].begin(),L[n].end(),make_tuple(m,0,0)));
					if(!(n>>=1)) break;
				}
				if(tot<b) s=m+1;
				else e=m-1;
			}
			n=SZ+a; e=tot=0;
			for(;;) {
				auto v=*--upper_bound(L[n].begin(),L[n].end(),make_tuple(s,0,0));
				if(get<0>(v)>tot) {
					tot=get<0>(v);
					e=get<1>(v);
				}
				if(!(n>>=1)) break;
			}
			cout<<e<<'\n';
		}
	}
	return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 45508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 45508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 227 ms 48456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1018 ms 74856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 45508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 440 ms 56304 KB Output is correct
2 Correct 452 ms 57268 KB Output is correct
3 Correct 448 ms 57728 KB Output is correct
4 Correct 315 ms 54712 KB Output is correct
5 Correct 451 ms 56488 KB Output is correct
6 Correct 479 ms 58312 KB Output is correct
7 Correct 175 ms 47224 KB Output is correct
8 Correct 168 ms 47124 KB Output is correct
9 Correct 226 ms 53084 KB Output is correct
10 Correct 212 ms 55340 KB Output is correct
11 Correct 264 ms 58748 KB Output is correct
12 Correct 270 ms 58684 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 45508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 45508 KB Output isn't correct
2 Halted 0 ms 0 KB -