Submission #1248440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248440		CrabCNH	Worst Reporter 3 (JOI18_worst_reporter3)	C++20	100 / 100	335 ms	26964 KiB

worst_reporter3

#include <bits/stdc++.h>

#define task     "BriantheCrab"

#define int    long long
#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}

const int maxN = 5e5 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

// khong tu code thi khong kha len duoc dau

struct Que {
    int t, l, r;
};

int n, q;
int d[maxN];
Que off[maxN];

namespace sub3 {
    
    int c[maxN];
    
    inline int bs (int x, int t) {
        int l = 0, r = n, res = n + 1;
        while (true) {
            if (l > r) {
                break;
            }
            int mid = (l + r) >> 1;
            //cout << l << ' ' << r << '\n';
            if (c[mid] * (t / c[mid]) - mid <= x) {
                res = mid;
                r = mid - 1;
            } 
            else {
                l = mid + 1;
            }
        }
        return n - res;
    }
        
    inline void sol () {
        c[0] = 1;
        for (int i = 1; i <= n; i ++) {
            c[i] = ((d[i] - 1) / c[i - 1] + 1) * c[i - 1]; 
        }
        sort (c, c + n + 1);
        for (int i = 1; i <= q; i ++) {
            auto [t, l, r] = off[i];
            cout << bs (r, t) - bs (l - 1, t) << '\n';
        }
    }
}

void solve () {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) {
        cin >> d[i];
    }
    for (int i = 1; i <= q; i ++) {
        int t, l, r;
        cin >> t >> l >> r;
        off[i] = {t, l, r};
    }
    sub3 :: sol ();
    return;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t --) {
        solve ();
    } 
    return 0;
}
// thfv

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:89:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp:90:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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