oj.uz

Submission #245993

# Submission time Handle Problem Language Result Execution time Memory
245993 2020-07-08T00:00:54 Z fivefourthreeone Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 625 ms 23416 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 20892 KB Output is correct
2 Correct 608 ms 20748 KB Output is correct
3 Correct 625 ms 20848 KB Output is correct
4 Correct 618 ms 20836 KB Output is correct
5 Correct 607 ms 20856 KB Output is correct
6 Correct 607 ms 20728 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 20892 KB Output is correct
2 Correct 608 ms 20748 KB Output is correct
3 Correct 625 ms 20848 KB Output is correct
4 Correct 618 ms 20836 KB Output is correct
5 Correct 607 ms 20856 KB Output is correct
6 Correct 607 ms 20728 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 398 ms 19320 KB Output is correct
14 Correct 428 ms 19832 KB Output is correct
15 Correct 396 ms 18680 KB Output is correct
16 Correct 402 ms 19064 KB Output is correct
17 Correct 495 ms 23288 KB Output is correct
18 Correct 524 ms 23292 KB Output is correct
19 Correct 483 ms 23416 KB Output is correct
20 Correct 509 ms 23288 KB Output is correct
21 Correct 487 ms 23288 KB Output is correct
22 Correct 500 ms 23416 KB Output is correct
23 Correct 489 ms 23288 KB Output is correct
24 Correct 494 ms 23416 KB Output is correct
25 Correct 617 ms 20728 KB Output is correct
26 Correct 600 ms 20984 KB Output is correct
27 Correct 522 ms 22900 KB Output is correct
28 Correct 552 ms 23136 KB Output is correct
29 Correct 523 ms 22772 KB Output is correct
30 Correct 532 ms 22904 KB Output is correct
31 Correct 554 ms 23284 KB Output is correct
32 Correct 485 ms 19448 KB Output is correct
33 Correct 5 ms 384 KB Output is correct