#694708 (C++17) No.1012 荷物収集

• 問題: No.1012 荷物収集
• ユーザー: snrnsidy
• 提出日時: 2021-09-02 11:52:46
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 64 ms / 2,000 ms
• コード長: 1,269 bytes
• コンパイル時間: 2,462 ms
• コンパイル使用メモリ: 214,356 KB
• 実行使用メモリ: 6,508 KB
• 最終ジャッジ日時: 2024-11-29 17:58:24
• 合計ジャッジ時間: 8,414 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	51 ms; 6,376 KB
testcase_05	AC	50 ms; 6,508 KB
testcase_06	AC	50 ms; 6,376 KB
testcase_07	AC	50 ms; 6,508 KB
testcase_08	AC	51 ms; 6,504 KB
testcase_09	AC	51 ms; 6,376 KB
testcase_10	AC	50 ms; 6,508 KB
testcase_11	AC	51 ms; 6,500 KB
testcase_12	AC	50 ms; 6,508 KB
testcase_13	AC	50 ms; 6,504 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	2 ms; 5,248 KB
testcase_17	AC	2 ms; 5,248 KB
testcase_18	AC	2 ms; 5,248 KB
testcase_19	AC	2 ms; 5,248 KB
testcase_20	AC	2 ms; 5,248 KB
testcase_21	AC	2 ms; 5,248 KB
testcase_22	AC	2 ms; 5,248 KB
testcase_23	AC	2 ms; 5,248 KB
testcase_24	AC	44 ms; 5,248 KB
testcase_25	AC	58 ms; 6,380 KB
testcase_26	AC	32 ms; 5,248 KB
testcase_27	AC	9 ms; 5,248 KB
testcase_28	AC	57 ms; 6,376 KB
testcase_29	AC	35 ms; 5,248 KB
testcase_30	AC	59 ms; 6,500 KB
testcase_31	AC	25 ms; 5,248 KB
testcase_32	AC	20 ms; 5,248 KB
testcase_33	AC	32 ms; 5,248 KB
testcase_34	AC	34 ms; 5,248 KB
testcase_35	AC	50 ms; 6,504 KB
testcase_36	AC	31 ms; 5,248 KB
testcase_37	AC	33 ms; 5,248 KB
testcase_38	AC	47 ms; 5,476 KB
testcase_39	AC	22 ms; 5,248 KB
testcase_40	AC	26 ms; 5,248 KB
testcase_41	AC	64 ms; 6,380 KB
testcase_42	AC	32 ms; 5,248 KB
testcase_43	AC	42 ms; 5,248 KB
testcase_44	AC	2 ms; 5,248 KB

ソースコード

#include <bits/stdc++.h>

using namespace std;

long long int res[100005];

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n, q, x, w, t;
	vector <pair<pair<int, int>, int>> v;

	cin >> n >> q;

	for (int i = 0; i < n; i++)
	{
		cin >> x >> w;
		v.push_back(make_pair(make_pair(x, 1), w));
	}

	for (int i = 0; i < q; i++)
	{
		cin >> t;
		v.push_back(make_pair(make_pair(t, 0), i));
	}

	sort(v.begin(), v.end());

	long long int sum = 0;
	long long int X = v[0].first.first;
	long long int val = 0;

	for (int i = 0; i < v.size(); i++)
	{
		long long int x = v[i].first.first;
		int sel = v[i].first.second;
		val += ((x - X) * sum);
		X = x;
		if (sel == 0)
		{
			int idx = v[i].second;
			res[idx] += val;
		}
		else
		{
			sum += v[i].second;
		}
		v[i].first.second = 1 - v[i].first.second;
	}

	sort(v.rbegin(), v.rend());

	sum = 0;
	X = v[0].first.first;
	val = 0;

	for (int i = 0; i < v.size(); i++)
	{
		long long int x = v[i].first.first;
		int sel = v[i].first.second;
		val += ((X - x) * sum);
		X = x;
		if (sel == 1)
		{
			int idx = v[i].second;
			res[idx] += val;
		}
		else
		{
			sum += v[i].second;
		}
		v[i].first.second = 1 - v[i].first.second;
	}

	for (int i = 0; i < q; i++)
	{
		cout << res[i] << '\n';
	}
	return 0;
}