답안 #660924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660924	2022-11-23T14:34:55 Z	rukashii	Meteors (POI11_met)	C++17	74 / 100	1136 ms	65536 KB

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int maxn = 3e5 + 2;
 
int n, m, a[maxn], q, tree[maxn];
vector <tuple<int, int, int>> query;
vector <int> st[maxn], check[maxn];
pair <int, int> b[maxn];
 
void update(int pos, int val)
{
	for (int i = pos; i <= m; i += (i & (-i)))
	{
		tree[i] += val;
	}
}
 
int get(int pos)
{
	int ret = 0;
	for (int i = pos; i >= 1; i -= (i & (-i)))
	{
		ret += tree[i];
	}
	
	return ret;
}
 
void query_apply(int i)
{
	auto [u, v, f] = query[i - 1];
	
	if (u <= v)
	{
		update(u, f);
		update(v + 1, -f);
	}
	else
	{
		update(1, f);
		update(v + 1, -f);
		update(u, f);
	}
}
 
signed main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	//freopen("input.inp", "r", stdin);
	//freopen("output.out", "w", stdout);
	
	cin >> n >> m;
	
	for (int i = 1, t; i <= m; i++)
	{
		cin >> t;
		
		st[t].push_back(i);
	}
	
	for (int i = 1; i <= n; i++)
		cin >> a[i];
		
	cin >> q;
	
	for (int i = 1; i <= q; i++)
	{
		int l, r, w;
		cin >> l >> r >> w;
		
		query.push_back({l, r, w});
	}
	
	for (int i = 1; i <= n; i++)
	{
	    b[i] = {1, q + 1};
	}
	
	int cnt = n;
	while (1)
	{
		bool kt = 0;
		memset(tree, 0, sizeof(tree));
		for (int i = 1; i <= q; i++)
			check[i].clear();
		
		for (int i = 1; i <= n; i++)
		{
			auto [l, r] = b[i];
			if (l < r)
			{
				int mid = (l + r) / 2;
				check[mid].push_back(i);
				kt = 1;
			}
		}
		
		if (!kt)
			break;
		
		for (int i = 1; i <= q; i++)
		{
			query_apply(i);
			
			for (int p : check[i])
			{
				int &l = b[p].first, &r = b[p].second;
				int mid = (l + r) / 2;
				
				int sum = 0;
				for (int child : st[p])
				{
					sum += get(child);
					if (sum >= a[p])
						break;
				}
				
				
				if (sum < a[p])
				{
					l = mid + 1;
				}
				else
				{
					r = mid;
				}
			}
		}
	}
	
	for (int i = 1; i <= n; i++)
        if (b[i].second <= q)
        	cout << b[i].second << '\n';
        else
        	cout << "NIE\n";
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:82:6: warning: unused variable 'cnt' [-Wunused-variable]
   82 |  int cnt = n;
      |      ^~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	16980 KB	Output is correct
2	Correct	10 ms	16852 KB	Output is correct
3	Correct	10 ms	16800 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	16852 KB	Output is correct
2	Correct	11 ms	16892 KB	Output is correct
3	Correct	11 ms	16852 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	19600 KB	Output is correct
2	Correct	103 ms	23044 KB	Output is correct
3	Correct	103 ms	21872 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	91 ms	21060 KB	Output is correct
2	Correct	100 ms	21012 KB	Output is correct
3	Correct	103 ms	23300 KB	Output is correct
4	Correct	34 ms	19952 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	78 ms	20148 KB	Output is correct
2	Correct	87 ms	23388 KB	Output is correct
3	Correct	49 ms	18364 KB	Output is correct
4	Correct	93 ms	22472 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	89 ms	18788 KB	Output is correct
2	Correct	95 ms	20940 KB	Output is correct
3	Correct	69 ms	19236 KB	Output is correct
4	Correct	110 ms	24536 KB	Output is correct

Subtask #7
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	966 ms	48336 KB	Output is correct
2	Correct	637 ms	30216 KB	Output is correct
3	Correct	217 ms	23176 KB	Output is correct
4	Runtime error	1136 ms	65536 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	965 ms	46396 KB	Output is correct
2	Correct	715 ms	30048 KB	Output is correct
3	Correct	183 ms	21800 KB	Output is correct
4	Runtime error	1091 ms	65536 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-