oj.uz

답안 #810903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810903 2023-08-06T17:17:02 Z parsadox2 푸드 코트 (JOI21_foodcourt) C++14
0 / 100
 473 ms 55804 KB 
#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn = 25e4 + 10;
int n , m , q , k[maxn] , c[maxn] , ans[maxn];
vector <int> ask[maxn] , all[2][maxn];

struct nod{
	int sum , sum_neg , suf_sum;
	nod()
	{
		sum = 0;
		sum_neg = 0;
		suf_sum = 0;
	}
} tree[maxn << 2];

nod Merge(nod a , nod b)
{
	nod res;
	res.sum_neg = a.sum_neg + b.sum_neg;
	res.sum = a.sum + b.sum;
	res.suf_sum = max(b.suf_sum , b.sum + a.suf_sum);
	return res;
}

void Add(int ind , int val , int ty = 1 , int node = 1 , int nl = 0 , int nr = q)
{
	if(nr - nl == 1)
	{
		tree[node].sum = ty * val;
		tree[node].sum_neg = min(0LL , tree[node].sum);
		tree[node].suf_sum = max(tree[node].sum , 0LL);
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(ind < mid)
		Add(ind , val , ty , lc , nl , mid);
	else
		Add(ind , val , ty , rc , mid , nr);
	tree[node] = Merge(tree[lc] , tree[rc]);
}

nod Get(int l , int r , int node = 1 , int nl = 0 , int nr = q)
{
	if(r <= nl || nr <= l)
	{
		nod tmp;
		return tmp;
	}
	if(l <= nl && nr <= r)
		return tree[node];
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	return Merge(Get(l , r , lc , nl , mid) , Get(l , r , rc , mid , nr));
}

int solve(int val)
{
	if(tree[1].suf_sum < val)
		return 0;
	int low = -1 , high = q - 1;
	while(high - low > 1)
	{
		int mid = (high + low) >> 1;
		nod g1 = Get(0 , mid + 1) , g2 = Get(mid + 1 , q);
		int tmp = g1.suf_sum + g2.sum_neg;
		if(tmp >= val)
			high = mid;
		else
			low = mid;
	}
	return c[high];
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout.tie(0);
	memset(ans , -1 , sizeof ans);
	cin >> n >> m >> q;
	for(int i = 0 ; i < q ; i++)
	{
		int ty;  cin >> ty;
		if(ty == 1)
		{
			int l , r;  cin >> l >> r >> c[i] >> k[i];
			all[0][l].push_back(i);
			all[1][r].push_back(i);
		}
		else if(ty == 2)
		{
			int l , r;  cin >> l >> r >> k[i];
			k[i] *= -1;
			all[0][l].push_back(i);
			all[1][r].push_back(i);
		}
		else
		{
			int a;  cin >> a >> k[i];
			ask[a].push_back(i);
		}
	}
	for(int i = 1 ; i <= n ; i++)
	{
		for(auto u : all[0][i])
		{
			//cout << "Hi Add" << endl;
			Add(u , k[u]);
			//cout << "Bye Add" << endl;
		}
		for(auto u : ask[i])
		{
			//cout << "Hi solve" << endl;
			ans[u] = solve(k[u]);
			//cout << "Bye solve" << endl;
		}
		for(auto u : all[1][i])
			Add(u , k[u] , 0);
	}
	for(int i = 0 ; i < q ; i++)  if(ans[i] != -1)
		cout << ans[i] << endl;
	return 0;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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