Submission #1247448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247448		AHOKA	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	171 ms	7372 KiB

worst_reporter3

#include <bits/stdc++.h>

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc + 1)

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

const int maxn = 1e6 + 10, maxm = 4e2 + 10, oo = 1e18 + 10, lg = 23, sq = 30, mod = 1e9 + 7;

int n, m, d, a[maxn];

struct grp
{
    int l;
    int r;
    int a;
} g;

vector<grp> v;

void solve(){
    cin >> n >> m;
    a[0] = 1;

    g.l = g.r = 0;
    g.a = 1;
    v.push_back(g);

    for (int i = 1; i <= n; i++){
        cin >> d;
        a[i] = a[i - 1] * ((d + a[i - 1] - 1) / a[i - 1]);

        if(a[i] == a[i - 1])
            v.back().r = i;
        else{
            g.l = g.r = i;
            g.a = min(mod, a[i]);
            v.push_back(g);
        }
    }

    while(m--){
        int ans = 0;
        int t, ql, qr;
        cin >> t >> ql >> qr;
        for(auto g : v){
            int cnt = (t / g.a);
            int d = cnt * g.a;
            int l = max(ql, -g.r + d);
            int r = min(qr, -g.l + d);
            ans += max(0ll, (r - l + 1));
        }
        cout << ans << "\n";
    }
}

signed main()
{
    threesum;

    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

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