oj.uz

Submission #946164

# Submission time Handle Problem Language Result Execution time Memory
946164 2024-03-14T11:26:11 Z pcc Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 416 ms 25628 KB 
#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;
		assert(step>0);
		//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(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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 7340 KB Output is correct
2 Correct 191 ms 7368 KB Output is correct
3 Correct 198 ms 7172 KB Output is correct
4 Correct 189 ms 7252 KB Output is correct
5 Correct 191 ms 7248 KB Output is correct
6 Correct 188 ms 7124 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 7340 KB Output is correct
2 Correct 191 ms 7368 KB Output is correct
3 Correct 198 ms 7172 KB Output is correct
4 Correct 189 ms 7252 KB Output is correct
5 Correct 191 ms 7248 KB Output is correct
6 Correct 188 ms 7124 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 203 ms 21360 KB Output is correct
14 Correct 205 ms 21876 KB Output is correct
15 Correct 176 ms 20488 KB Output is correct
16 Correct 191 ms 21040 KB Output is correct
17 Correct 360 ms 25204 KB Output is correct
18 Correct 399 ms 25168 KB Output is correct
19 Correct 399 ms 25628 KB Output is correct
20 Correct 358 ms 25264 KB Output is correct
21 Correct 364 ms 25328 KB Output is correct
22 Correct 353 ms 25452 KB Output is correct
23 Correct 349 ms 25144 KB Output is correct
24 Correct 357 ms 25620 KB Output is correct
25 Correct 208 ms 22608 KB Output is correct
26 Correct 205 ms 22608 KB Output is correct
27 Correct 373 ms 24744 KB Output is correct
28 Correct 409 ms 25256 KB Output is correct
29 Correct 402 ms 24624 KB Output is correct
30 Correct 395 ms 24916 KB Output is correct
31 Correct 416 ms 25424 KB Output is correct
32 Correct 194 ms 21328 KB Output is correct
33 Correct 0 ms 348 KB Output is correct