Submission #245993

#	Time	Username	Problem	Language	Result	Execution time	Memory
245993		fivefourthreeone	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	625 ms	23416 KiB

worst_reporter3

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 500001;
int n, q;
int arr[mxN];
int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>q;
    owo(i, 1, n+1) {
        cin>>arr[i];
    }
    arr[0] = 1;
    owo(i, 1, n+1) {
        if(arr[i-1]>=1000000001) arr[i] = 1000000001;
        else {
            arr[i] = arr[i-1]*((arr[i]+arr[i-1]-1)/arr[i-1]);
        }
    }
    int t, left, right;
    while(q--) {
        cin>>t>>left>>right;
        int pos = t;
        if(pos<left) {
            cout<<"0\n";
            continue;
        }
        pos= t/arr[n]*arr[n]-n;
        if(pos>right) {
            cout<<"0\n";
            continue;
        }
        int first = 0;
        int second = 0;
        int l = 0;
        int r = n;
        while(l<r) {
            int mid = (l+r+1)/2;
            //cout<<mid<<" "<<(-mid+t/arr[mid]*arr[mid])<<"\n";
            if(-mid+t/arr[mid]*arr[mid]>=left) {
                l = mid;
            }else {
                r=mid-1;
            }
        }
        first = l;
        l = 0;
        r = n;
        while(l<r) {
            int mid = (l+r)/2;
            if(-mid+t/arr[mid]*arr[mid]<=right)r = mid;
            else l = mid+1;
        }
        if(l>first) {
            cout<<"0\n";
        }else {
            cout<<(first-l+1)<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

worst_reporter3.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
worst_reporter3.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:53:13: warning: unused variable 'second' [-Wunused-variable]
         int second = 0;
             ^~~~~~

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