Submission #331057

#	Time	Username	Problem	Language	Result	Execution time	Memory
331057		pit4h	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	100 / 100	807 ms	37356 KiB

worst_reporter3

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 5e5+1, inf = 1e9+1;
int n, q;
int d[N];
int ans[N];
struct Q {
	int t, l, r, id;
	bool operator<(const Q& o) const {
		return t < o.t;
	}
};
vector<Q> queries;

pii jump[N]; // st - dist, nd - t
ll get_pos(int x, int t) {
	return -x + jump[x].st * (t/jump[x].nd);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>q;	
	for(int i=1; i<=n; ++i) {
		cin>>d[i];
	}

	jump[0] = mp(1, 1);
	for(int i=1; i<=n; ++i) {
		jump[i] = mp(0, inf);
		ll lo = 1, hi = inf, mid;
		while(lo<=hi) {
			mid = (lo+hi)/2;
			if(get_pos(i-1, mid) - (-i) > d[i]) {
				jump[i] = mp(get_pos(i-1, mid)-1 - (-i), mid);
				hi = mid-1;
			}
			else {
				lo = mid+1;
			}
		}
	}

	queries.resize(q);
	for(int i=0; i<q; ++i) {
		cin>>queries[i].t>>queries[i].l>>queries[i].r;
		queries[i].id = i;
	}
	sort(queries.begin(), queries.end());
	
	for(auto qry: queries) {
		auto bs = [](bool find_leftmost, Q& qq)->int {
			int lo = 0, hi = n, mid;
			int res = -1;
			while(lo<=hi) {
				mid = (lo+hi)/2;
				if(get_pos(mid, qq.t) < qq.l) {
					hi = mid-1;
				}
				else if(get_pos(mid, qq.t) > qq.r) {
					lo = mid+1;
				}
				if(get_pos(mid, qq.t) >= qq.l && get_pos(mid, qq.t) <= qq.r) {
					res = mid;
					if(find_leftmost) hi = mid-1;	
					else lo = mid+1;
				}
			}
			return res;
		};
		int leftmost = bs(1, qry);
		int rightmost = bs(0, qry);
		if(leftmost == -1) ans[qry.id] = 0;
		else {
			ans[qry.id] = rightmost - leftmost + 1;
		}
	}
	for(int i=0; i<q; ++i) {
		cout<<ans[i]<<'\n';
	}
}

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