Submission #946162

#	Time	Username	Problem	Language	Result	Execution time	Memory
946162		pcc	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	19 / 100	204 ms	23072 KiB

worst_reporter3

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const ll mxn = 5e5+10;
ll arr[mxn];
ll N,Q;
vector<pair<ll,pll>> v;

vector<pll> calc(ll t){
	vector<pll> re = {pll(t,t)};
	ll now = t-1;
	for(auto [step,r]:v){
		if(now<=0)break;
		//cerr<<t<<":"<<i.fs<<','<<i.sc<<"::"<<now<<','<<now/arr[i.fs]*arr[i.fs]-i.sc+i.fs-1<<endl;
		now = -r.fs+(now+r.fs)/step*step;
		if(now<=0)break;
		re.push_back(pll(now-(r.sc-r.fs),now));
		now = re.back().fs-1;
	}
	reverse(re.begin(),re.end());
	//cerr<<t<<":";for(auto &i:re)cerr<<i.fs<<' '<<i.sc<<',';cerr<<endl;
	return re;
}

void solve(){
	ll t,l,r;
	cin>>t>>l>>r;
	auto vv = calc(t);
	ll ans = 0;
	//for(auto &i:vv)cerr<<i.fs<<' '<<i.sc<<',';cerr<<endl;
	for(auto &i:vv){
		if(i.sc<l||i.fs>r)continue;
		ans += min(i.sc,r)-max(l-1,i.fs-1);
	}
	cout<<ans<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	ll d = 0;
	for(int i = 1;i<=N;i++){
		cin>>arr[i];
		if(v.empty())d = arr[i],v.push_back(make_pair(arr[i],pll(i,i)));
		else if(arr[v.back().fs]>arr[i])v.back().sc.sc = i;
		else if(d<arr[i]){
			d = (arr[i]+d-1)/d*d;
			v.push_back(make_pair(d,pll(i,i)));
		}
		else v.back().sc.sc = i;
		//cout<<i<<":"<<d<<endl;
	}
	//for(auto &i:v)cout<<i.fs<<','<<i.sc<<":"<<arr[i.fs]<<endl;
	while(Q--)solve();
}

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