답안 #94596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94596 2019-01-21T14:35:31 Z aminra Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
454 ms 29116 KB
//Smaug never desolated!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)5e5 + 7;
const int infint = (int)1e9 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e18;
ll a[MAXN], n, tme[MAXN], Q;
ll intersect(ll u, ll v, ll a, ll b)
{
	ll mx = max(u, a);
	ll mn = min(v, b);
	if(mn >= mx)
		return mn - mx + 1;
	else
		return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> Q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	tme[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		ll tmp = (a[i] + tme[i - 1] - 1) / tme[i - 1];
		tme[i] = tme[i - 1] * tmp;
		if(tme[i] >= infint)	
			break;
	}
	int last = 0;
	vector< pair<ll, pair<ll, ll> > > v;
	v.push_back({1, {0, 0}});
	for (int i = 1; i <= n; i++)
	{
		if(tme[i] >= infint)
			break;
		if(tme[i] == tme[last])
			v.back().second.second++;
		else
			v.push_back({tme[i], {i, i}}), last = i;
	}
	for (int i = 0; i < Q; i++)
	{
		ll L, R, T;
		cin >> T >> L >> R;
		ll ans = 0;
		for (auto u : v)
		{
			ll cur = (T / u.first) * u.first;
			ll newL = 0, newR = 0;
			if(L <= cur && cur <= R)
				newL = 0, newR = cur - L;
			else
			if(cur > R)
				newL = cur - R, newR = cur - L;
			else
				newL = -1, newR = -1;
			ans += intersect(u.second.first, u.second.second, newL, newR);	
		}
		cout << ans << "\n";
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 25336 KB Output is correct
2 Correct 265 ms 26616 KB Output is correct
3 Correct 258 ms 26616 KB Output is correct
4 Correct 262 ms 26616 KB Output is correct
5 Correct 261 ms 26764 KB Output is correct
6 Correct 261 ms 26616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 25336 KB Output is correct
2 Correct 265 ms 26616 KB Output is correct
3 Correct 258 ms 26616 KB Output is correct
4 Correct 262 ms 26616 KB Output is correct
5 Correct 261 ms 26764 KB Output is correct
6 Correct 261 ms 26616 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 264 ms 21212 KB Output is correct
14 Correct 268 ms 21824 KB Output is correct
15 Correct 247 ms 20472 KB Output is correct
16 Correct 262 ms 20976 KB Output is correct
17 Correct 442 ms 28176 KB Output is correct
18 Correct 411 ms 28128 KB Output is correct
19 Correct 415 ms 27640 KB Output is correct
20 Correct 414 ms 28252 KB Output is correct
21 Correct 408 ms 28084 KB Output is correct
22 Correct 412 ms 27668 KB Output is correct
23 Correct 416 ms 28448 KB Output is correct
24 Correct 415 ms 27580 KB Output is correct
25 Correct 269 ms 26572 KB Output is correct
26 Correct 271 ms 26540 KB Output is correct
27 Correct 422 ms 28616 KB Output is correct
28 Correct 454 ms 29116 KB Output is correct
29 Correct 431 ms 26376 KB Output is correct
30 Correct 431 ms 27100 KB Output is correct
31 Correct 440 ms 28944 KB Output is correct
32 Correct 261 ms 25304 KB Output is correct
33 Correct 2 ms 376 KB Output is correct