제출 #777616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777616		vjudge1	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	311 ms	20736 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;

const int NM = 5e5;

int N, Q, D[NM+5];
int M = 1, L[NM+5], R[NM+5];

int inter(int l, int r, int u, int v){
	return max(0, min(v, r)-max(u, l)+1);
}

int query(int T, int U, int V){
	int res = inter(T-R[1], T, U, V), cur = T-R[1];
	for (int i = 2; i <= M; i++){
		cur = ((cur+L[i]-1)/D[L[i]])*D[L[i]]-R[i];
		res += inter(cur, cur+R[i]-L[i], U, V);
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	D[0] = 1;
	for (int i = 1; i <= N; i++){
		cin >> D[i];
		D[i] = (D[i]/D[i-1]+(D[i]%D[i-1] > 0))*D[i-1];
	}
	L[1] = 0;
	for (int i = 1; i <= N; i++)
		if (D[i] > D[i-1]){
			M++;
			R[M-1] = i-1;
			L[M] = i;
		}
	R[M] = N;
	while (Q--){
		int T, U, V;
		cin >> T >> U >> V;
		cout << query(T, U, V) << '\n';
	}
	return 0;//
}

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