oj.uz

답안 #810927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810927 2023-08-06T17:39:28 Z parsadox2 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 383 ms 60056 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 = 1LL * 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) , check2 = Get(ind , q);
	int val = k[ind];
	if(check.suf_sum + check2.sum_neg < 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] = -1LL * k[i];
			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 21 ms 43492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 47964 KB Output is correct
2 Correct 198 ms 47548 KB Output is correct
3 Correct 196 ms 47592 KB Output is correct
4 Correct 141 ms 46540 KB Output is correct
5 Correct 185 ms 47136 KB Output is correct
6 Correct 196 ms 47564 KB Output is correct
7 Correct 154 ms 45992 KB Output is correct
8 Correct 147 ms 45844 KB Output is correct
9 Correct 195 ms 46668 KB Output is correct
10 Correct 131 ms 46068 KB Output is correct
11 Correct 190 ms 46772 KB Output is correct
12 Correct 193 ms 47036 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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