Submission #43996

#	Time	Username	Problem	Language	Result	Execution time	Memory
43996		zscoder	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	849 ms	11580 KiB

worst_reporter3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

ll d[511111];
int n,q; 
ll period[511111];
vector<pair<ll,ii> > segments;

ll solve(ll t, ll x)
{
	//check IOI-chan separately :)
	ll ans = 0;
	if(t<=x) ans++;
	/*noob solution
	for(int i=1;i<=n;i++)
	{
		//calculate position after t seconds
		ll pos = -i + (t/period[i])*period[i];
		ans+=(pos<=x);
	}
	*/
	for(int i=0;i<segments.size();i++)
	{
		ll per = segments[i].fi; ll l = segments[i].se.fi; ll r = segments[i].se.se;
		ll extramoves = (t/per)*per;
		extramoves -= x;
		//count # of [l,r] which is >= extramoves
		if(l>=extramoves) ans+=(r-l+1);
		else if(r>=extramoves)
		{
			ans += (r-extramoves+1);
		}
	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>d[i];
	period[1] = d[1];
	ll cur = d[1]; int pre = 1;
	for(int i = 2; i <= n; i++)
	{
		ll ext = (d[i] + cur - 1)/cur;
		period[i] = ext*cur;
		if(period[i]>cur)
		{
			segments.pb(mp(cur, mp(pre, i - 1)));
			pre = i;
		}
		cur = period[i];
	}
	segments.pb(mp(cur, mp(pre, n)));
	//do stupid solution first
	for(int i=0;i<q;i++)
	{
		ll t,l,r; cin>>t>>l>>r;
		cout<<solve(t,r)-solve(t,l-1)<<'\n';
	}
}	

Compilation message (stderr)

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

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