제출 #1029957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029957		underwaterkillerwhale	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	348 ms	15352 KiB

worst_reporter3

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 5e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 320;
const ll INF = 1e9 + 160907;
const int BASE = 1337;

int n, Q, m;
int D[N];
int dp[N];
int T[N], L[N], R[N];
map<int, pair<int,int>> itv;

void solution () {
    cin >> n >> Q;
    ++n;
    D[1] = 1;
    rep (i, 2, n) {
        cin >> D[i];
    }
    dp[1] = 1;
    vector<int> vals;
    vals.push_back(1);
    itv[1] = {1, 1};
    rep (i, 2, n) {
        dp[i] = min (INF, (ll) (dp[i - 1] * ceil(1.0 * D[i] / D[i - 1])));
        D[i] = min (INF, (ll) (ceil(1.0 * D[i] / D[i - 1]) * D[i - 1]));
        vals.push_back(dp[i]);
        if (itv[dp[i]].fs == 0) itv[dp[i]] = {i, i};
        else itv[dp[i]].se = i;
    }
    sort (ALL(vals));
    vals.resize (m = unique(ALL(vals)) - vals.begin());
    rep (i, 1, Q) {
        cin >> T[i] >> L[i] >> R[i];
        int res = 0;
        iter (&vl, vals) {
            int lf = itv[vl].fs, rt = itv[vl].se;
            int bL = max(1LL * lf, 1LL * (T[i] / vl) * D[lf] + 1 - R[i]);
            int bR = min(1LL * rt, 1LL * (T[i] / vl) * D[lf] + 1 - L[i]);
            res += max(0, bR - bL + 1);
        }
        cout << res <<"\n";
    }
}

#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
nếu mình nghĩ sẽ thay đổi định nghĩa, kiểu dữ liệu của hàm hay mảng j thì mình phải nghĩ xem nó sẽ ảnh hưởng đến các phần nào
nghĩ xem mình có thể làm gì, có khả năng làm những gì với giới hạn bài toán, đặc điểm bài toans
0 0
1 0
0 0
*/

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