Submission #1177390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177390		ByeWorld	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	169 ms	11360 KiB

worst_reporter3

#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 5e5+10;
const int MAXA = 1e9;
const int INF = 1e9+100;
const int SQRT = 500;
const int LOG = 61;
const int MOD = 1e9+7;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }
int sum(int a, int b){ a %= MOD; b %= MOD; return (a+b)%MOD; }
int sub(int a, int b){ a %= MOD; b %= MOD; return (a+MOD-b)%MOD; }
void chsum(int &a, int b){ a %= MOD; b %= MOD; a = (a+b)%MOD; }
void chsub(int &a, int b){ a %= MOD; b %= MOD; a = (a+MOD-b)%MOD; }
int mul(int a, int b){ a %= MOD; b %= MOD; return a*b%MOD;}
void chmul(int &a, int b){ a = a*b%MOD; }
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te, te);
	return (b%2 ? mul(te, a) : te);
}

int n, q, d[MAXN], jump[MAXN];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1; i<=n; i++) cin>>d[i];
	int nw = 1;
	for(int i=1; i<=n; i++){
		if(nw > MAXA){
			jump[i] = nw; continue;
		}
		if(nw >= d[i]) jump[i] = nw;
		else jump[i] = ((d[i]+nw-1)/nw)*nw;
		nw = jump[i];
		// cout << i << ' ' << jump[i] << " ju\n";
	}
	jump[0] = 1;
	vector<pii> vec;
	for(int i=0; i<=n; ){
		int j = i;
		while(i<=n && jump[i]==jump[j]){
			i++;
		}
		vec.pb({j, i-1});
		// cout << j << ' ' << i-1 << "j\n";
	}
	while(q--){
		int tim, l, r; cin>>tim>>l>>r;
		int ans = 0;
		for(auto [x, y] : vec){
			int j = jump[x];
			int add = (tim/j)*j;
			// -y -- -x, +add
			int le = -y+add, ri = -x+add;
			ans += max(0ll, min(r,ri)-max(l,le)+1);
		}
		cout << ans << '\n';
	}
}

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