Submission #198025

#	Time	Username	Problem	Language	Result	Execution time	Memory
198025		AMO5	Worst Reporter 3 (JOI18_worst_reporter3)	C++98	100 / 100	1852 ms	29340 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

long long INF=LLONG_MAX;

ll n,q,d[511111],per[511111];
ll md=0;
vector < pair<ll, pll> > seg;

void upd(){
	ll cur = d[1], pre = 1;
	per[1] = d[1];
	for(ll i = 2; i <= n; i++){
		ll tm = (cur>=d[i]?1:d[i]/cur+(d[i]%cur?1:0));
		per[i] = tm*cur;
		if(per[i]>cur){
			seg.pb(mp(cur,mp(pre,i-1)));
			pre = i;
			cur = per[i];
		}
	}
	seg.pb(mp(cur,mp(pre,n)));
}

ll solve(ll ti, ll x, ll y){
	ll ans = 0;
	if(ti>=x&&ti<=y)ans++;
	for(int i = 0; i < seg.size(); i++){
		ll cur = seg[i].fi; ll le = seg[i].se.fi; ll ri = seg[i].se.se;
		ll moves = (ti/cur)*cur;
		//cout << i << ' ' << cur << ' ' << le << ' ' << ri << ' ' << moves << endl;
		ll pos_l = -1*ri; ll pos_r = -1*le;
		pos_l += moves; pos_r += moves;
		//cout << ' ' << pos_l << ' ' << pos_r;
		pos_l=max(pos_l,x);
		pos_r=min(pos_r,y);
		//cout << ' ' << pos_l << ' ' << pos_r << endl;
		if(pos_l>=x&&pos_l<=y&&pos_r>=x&&pos_r<=y){
			ans += pos_r-pos_l+1;
		}
	}
	return ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> d[i];
		md = max(md,d[i]);
	}
	upd();
	ll ti,le,ri;
	//for(int i = 1; i <= n; i++)cout << per[i] << ' '; 
	//cout << endl;
	while(q--){
		cin >> ti >> le >> ri;
		ll ans = 0;
		ans += solve(ti,le,ri);
		cout << ans << endl;
	}
}	

Compilation message (stderr)

worst_reporter3.cpp: In function 'll solve(ll, ll, ll)':
worst_reporter3.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < seg.size(); i++){
                 ~~^~~~~~~~~~~~

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