結果

問題 No.3284 Picnic with Friends
コンテスト
ユーザー Carpenters-Cat
提出日時 2025-09-26 23:04:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,705 ms / 7,000 ms
コード長 1,121 bytes
コンパイル時間 2,311 ms
コンパイル使用メモリ 209,444 KB
実行使用メモリ 14,792 KB
最終ジャッジ日時 2025-10-08 17:01:44
合計ジャッジ時間 52,270 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
	int N;
	cin >> N;
	std::vector<ll> S(N);
	for (ll& a : S) cin >> a;
	vector<int> ID(N);
	iota(ID.begin(), ID.end(), 0);
	{
		auto IDD = ID;
		sort(IDD.begin(), IDD.end(), [&](int i, int j) {return S[i] < S[j];});
		for (int i = 0; i < N; i ++) {
			ID[IDD[i]] = i;
		}
	}
	sort(S.begin(), S.end());
	vector<ll> TL;
	int Q;
	cin >> Q;
	{
		ll b = 0, e = 0, n = 0;
		while (Q--) {
			ll t, f;
			cin >> t >> f;
			if (e >= t) {
				e += f;
			} else {
				if (e - b) TL.push_back(e - b);
				b = t; e = t + f;
			}
			n = t;
		}
		if (e - b) TL.push_back(e - b);
	}
	vector<ll> ans(1000, 0);
	for (int i = 1; i < 1000; i ++) {
		for (auto& f : TL) {
			ans[i] += f / i;
		}
	}
	vector<ll> A2(N + 1, 0);
	for (auto& f : TL) {
		for (ll s = 1; s * 1000 <= f; s ++) {
			ll d = f / s;
			A2[0] ++;
			int i = upper_bound(S.begin(), S.end(), d) - S.begin();
			A2[i] --;
		}
	}
	for (int i = 1; i <= N; i ++) A2[i] += A2[i-1];
	for (int& a : ID) {
		if (S[a] < 1000) {
			cout << ans[S[a]] << endl;
		} else {
			cout << A2[a] << endl;
		}
	}
}
0