Submission #915596

#	Time	Username	Problem	Language	Result	Execution time	Memory
915596		boris_mihov	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	295 ms	23528 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

worst_reporter3

#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())
      |         ~~^~~~~~~~~~~~

Subtask 17 / 7

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 212 / 12

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 381 / 81

#	Verdict	Execution time	Memory	Grader output
Fetching results...