Submission #624995

#	Time	Username	Problem	Language	Result	Execution time	Memory
624995		Arnch	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	19 / 100	2052 ms	13148 KiB

worst_reporter3

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int a[N], d[N];
int T[N], L[N], R[N];
map<int, pair<int, int> > s;

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
	
	int n, q; cin >>n >>q;
	for(int i = 1; i <= n; i++) cin >>a[i];

	bool f = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i] > 1) f = 1;
	}

	d[1] = a[1];
	for(int i = 2; i <= n; i++) {
		if(a[i] <= a[i - 1]) {
			d[i] = d[i - 1];
			continue;
		}
		ll cnt = a[i] / d[i - 1];
		if(cnt * d[i - 1] < a[i]) cnt++;
		d[i] = d[i - 1] * cnt;
	}

	vector<int> vc;
	for(int i = 1; i <= n;) {
		if(d[i] > 1e9) continue;
		int ptr = i;
		while(ptr <= n && d[ptr] == d[i]) ptr++;
		s[d[i]] = make_pair(i, ptr - 1);
		vc.push_back(d[i]);
		i = ptr;
	}
	sort(All(vc)), vc.erase(unique(All(vc)), vc.end());

	if(f && n > 1000) {
		assert(0);
	}

	for(int j = 0; j < q; j++) {
		cin >>T[j] >>L[j] >>R[j];
		int ans = 0;
		for(auto i : vc) {
			if(i > T[j]) break;
			int cnt = (T[j] / i) * i;
			int l = cnt + -s[i].second, r = cnt + -s[i].first;
			if(r < L[j] || l > R[j]) continue;
			if(r >= R[j] && l <= L[j]) {
				ans += R[j] - L[j] + 1;
				continue;
			}
			if(R[j] >= r && L[j] <= l) {
				ans += r - l + 1;
				continue;
			}
			if(r <= R[j]) ans += r - L[j] + 1;
			else ans += R[j] - l + 1;
		}
		cout<<ans + (T[j] >= L[j] && T[j] <= R[j]) <<endl;
	}
		
    return 0;
}

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