This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 500000 + 10;
const int INF = 1e9;
int n, q;
int d[MAXN];
struct Head
{
int idx;
int count;
int len;
int get(int time, int cnt)
{
assert(cnt <= len);
int jumpTimes = time / d[n];
jumpTimes -= jumpTimes % count;
return -(n - idx + 1) + jumpTimes * d[n] - cnt;
}
};
std::vector <Head> st;
int countTo(int to, int time)
{
int l = -1, r = st.size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (st[mid].get(time, 0) > to) l = mid;
else r = mid;
}
int res = 0;
if (r != st.size())
{
res += st[r].idx;
}
if (l != -1)
{
res += std::max(0, to + 1 - st[l].get(time, st[l].len - 1));
}
return res;
}
void solve()
{
std::reverse(d + 1, d + 1 + n);
st.push_back({n, 1, 1});
for (int i = n - 1 ; i >= 1 ; --i)
{
if (d[i] / (st.back().count * d[n]) + ((d[i] % (st.back().count * d[n])) > 0) > 1)
{
st.push_back({i, (d[i] / (st.back().count * d[n]) + ((d[i] % (st.back().count * d[n])) > 0)) * st.back().count, 1});
} else
{
st.back().len++;
}
}
for (int i = 1 ; i <= q ; ++i)
{
int l, r, pos;
std::cin >> pos >> l >> r;
int res = 0;
res += (l <= pos && pos <= r);
res += countTo(r, pos);
res -= countTo(l - 1, pos);
std::cout << res << '\n';
}
}
void input()
{
std::cin >> n >> q;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> d[i];
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message (stderr)
worst_reporter3.cpp: In function 'int countTo(int, int)':
worst_reporter3.cpp:41:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Head>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | if (r != st.size())
| ~~^~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
