Submission #520124

#	Time	Username	Problem	Language	Result	Execution time	Memory
520124		ymm	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	324 ms	23304 KiB

worst_reporter3

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 5e5+10;
const int M = 1e9+10;
int a[N];
vector<pair<pii,int>> vec;
int n, q;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> q;
	Loop(i,0,n) cin >> a[i];
	Loop(i,1,n) a[i] = min(M, a[i]%a[i-1]? a[i]+a[i-1]-(a[i]%a[i-1]): a[i]);
	for(int l=0,r=1;r<=n;++r){
		if(r==n||a[r]!=a[l]){
			vec.push_back({{-r, -l}, a[l]});
			l = r;
		}
	}
	while(q--){
		int l, r, t;
		cin >> t >> l >> r; ++r;
		int ans = l<=t&&t<r;
		for(auto [pr, x] : vec){
			auto [b, e] = pr;
			x = t-t%x;
			e = min(e+x, r);
			b = max(b+x, l);
			ans += max(0, e-b);
		}
		cout << ans << '\n';
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81