oj.uz

답안 #810907

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810907 2023-08-06T17:21:24 Z parsadox2 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 679 ms 55892 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 ind)
{
	nod check = Get(0 , ind);
	int val = k[ind];
	if(check.suf_sum < val)
		return 0;
	int low = -1 , high = ind - 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(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 18 ms 43436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 46556 KB Output is correct
2 Correct 196 ms 48380 KB Output is correct
3 Correct 245 ms 48448 KB Output is correct
4 Correct 142 ms 46956 KB Output is correct
5 Correct 170 ms 47784 KB Output is correct
6 Correct 204 ms 48424 KB Output is correct
7 Correct 157 ms 46376 KB Output is correct
8 Correct 149 ms 46232 KB Output is correct
9 Correct 221 ms 47432 KB Output is correct
10 Correct 178 ms 46356 KB Output is correct
11 Correct 212 ms 47652 KB Output is correct
12 Correct 188 ms 47564 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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