답안 #715127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715127	2023-03-26T00:09:26 Z	aryan12	Meteors (POI11_met)	C++17	74 / 100	1250 ms	65536 KB

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 3e5 + 5;
vector<int> bit(N);
int n, m;

void Update(int pos, int val)
{
	for(int i = pos; i > 0; i -= (i & (-i)))
	{
		bit[i] += val;
	}
}

int Query(int pos)
{
	if(pos == 0) return 0;
	int ans = 0;
	for(int i = pos; i < m + 5; i += (i & (-i)))
	{
		ans += bit[i];
	}
	return ans;
}

void Update(int l, int r, int val)
{
	if(r < l)
	{
		Update(r, val);
		// cout << "Update(" << r << ", " << val << ")\n";
		r = m;
	}
	// cout << "Update(" << r << ", " << val << ")\n";
	Update(r, val);
	// cout << "Update(" << l - 1 << ", " << -val << ")\n";
	Update(l - 1, -val);
}

void Solve() 
{
	cin >> n >> m;
	bit.resize(m + 5);
	vector<int> sector[n + 1];
	vector<int> requirements(n + 1);
	for(int i = 1; i <= m; i++)
	{
		int x;
		cin >> x;
		// cout << "x = " << x << ", i = " << i << "\n";
		sector[x].push_back(i);
	}
	for(int i = 1; i <= n; i++)
	{
		bit[i] = 0;
		cin >> requirements[i];
	}
	bit[0] = 0;
	int k;
	cin >> k;
	vector<array<int, 3> > queries(k + 1);
	vector<array<int, 3> > ranges(n + 1);
	vector<int> middle[k + 1];
	for(int i = 1; i <= k; i++)
	{
		cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
	}
	for(int i = 1; i <= n; i++)
	{
		ranges[i] = {1, k, k + 1};
	}
	while(true)
	{	
		int cnt = 0;
		for(int i = 0; i <= k; i++)
		{
			middle[i].clear();
		}
		for(int i = 0; i < m + 5; i++)
		{
			bit[i] = 0;
		}
		for(int i = 1; i <= n; i++)
		{
			if(ranges[i][0] > ranges[i][1])
			{
				cnt++;
			}
			else
			{
				int mid = (ranges[i][0] + ranges[i][1]) / 2;
				// cout << "i = " << i << ", ranges[i][0] = " << ranges[i][0] << ", ranges[i][1] = " << ranges[i][1] << ", mid = " << mid << endl;
				middle[mid].push_back(i);
			}
		}
		if(cnt == n)
		{
			break;
		}
		for(int i = 1; i <= k; i++)
		{
			Update(queries[i][0], queries[i][1], queries[i][2]);
			// for(int j = 1; j <= m; j++)
			// {
			// 	cout << Query(j) << " ";
			// }
			// cout << "\n";
			for(int j: middle[i])
			{
				int f = 0, gathered = 0;
				for(int cur: sector[j])
				{
					gathered += Query(cur);
					// cout << "Query(cur) = " << Query(cur) << "\n";
					// cout << "position = " << cur << ", gathered = " << gathered << "\n";
					if(gathered >= requirements[j])
					{
						ranges[j][1] = i - 1;
						ranges[j][2] = i;
						f = 1;
						break;
					}
				}
				// cout << "gathered = " << gathered << ", query number = " << i << ", organization number = " << j << "\n";
				if(f == 0)
				{
					ranges[j][0] = i + 1;
				}
			}
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(ranges[i][2] == k + 1)
		{
			cout << "NIE\n";
		}
		else
		{
			cout << ranges[i][2] << "\n";
		}
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2772 KB	Output is correct
2	Correct	3 ms	2824 KB	Output is correct
3	Correct	2 ms	2692 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2772 KB	Output is correct
2	Correct	3 ms	2820 KB	Output is correct
3	Correct	3 ms	2900 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	6672 KB	Output is correct
2	Correct	98 ms	11812 KB	Output is correct
3	Correct	90 ms	10104 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	75 ms	8168 KB	Output is correct
2	Correct	80 ms	9292 KB	Output is correct
3	Correct	79 ms	12056 KB	Output is correct
4	Correct	30 ms	6908 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	7120 KB	Output is correct
2	Correct	74 ms	12304 KB	Output is correct
3	Correct	37 ms	5692 KB	Output is correct
4	Correct	80 ms	10988 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	5624 KB	Output is correct
2	Correct	73 ms	9252 KB	Output is correct
3	Correct	58 ms	7144 KB	Output is correct
4	Correct	103 ms	13428 KB	Output is correct

Subtask #7
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	907 ms	43796 KB	Output is correct
2	Correct	344 ms	27084 KB	Output is correct
3	Correct	185 ms	16924 KB	Output is correct
4	Runtime error	1250 ms	65536 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	992 ms	41416 KB	Output is correct
2	Correct	239 ms	25724 KB	Output is correct
3	Correct	156 ms	15552 KB	Output is correct
4	Runtime error	1100 ms	65536 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

답안 #715127

Compilation message