oj.uz

Submission #946162

# Submission time Handle Problem Language Result Execution time Memory
946162 2024-03-14T11:24:12 Z pcc Worst Reporter 3 (JOI18_worst_reporter3) C++17
19 / 100
 204 ms 23072 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;
		//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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 22672 KB Output is correct
2 Correct 191 ms 22648 KB Output is correct
3 Correct 192 ms 22612 KB Output is correct
4 Correct 196 ms 22652 KB Output is correct
5 Correct 191 ms 22712 KB Output is correct
6 Correct 190 ms 23072 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 344 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 480 KB Output is correct

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 22672 KB Output is correct
2 Correct 191 ms 22648 KB Output is correct
3 Correct 192 ms 22612 KB Output is correct
4 Correct 196 ms 22652 KB Output is correct
5 Correct 191 ms 22712 KB Output is correct
6 Correct 190 ms 23072 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 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 480 KB Output is correct
13 Runtime error 1 ms 604 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -