oj.uz

Submission #797914

# Submission time Handle Problem Language Result Execution time Memory
797914 2023-07-30T06:53:09 Z vjudge1 Worst Reporter 3 (JOI18_worst_reporter3) C++14
0 / 100
 438 ms 26928 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 5e5 ;
ll n, q, tn, d[N + 1], ans[N + 1], pref[N + 1] ;
struct query
{
    ll t, l, r, ind ;
};
vector<query> qr ;
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> q ;
    for(ll i = 1 ; i <= n ; i++)
    {
        cin >> d[i] ;
        d[i]++ ;
    }
    d[1]-- ;
    for(ll i = 1 ; i <= q ; i++)
    {
        query q ;
        cin >> q.t >> q.l >> q.r ;
        q.ind = i ;
        qr.push_back(q) ;
    }
    pref[1] = d[1] ;
    for(ll i = 2 ; i <= n ; i++)
    {
        ll l = 0, r = 1e9 + 1 ;
        while(l + 1 < r)
        {
            ll mid = (l + r) >> 1 ;
            if(mid * pref[i - 1] >= d[i])r = mid ;
            else l = mid ;
        }
        pref[i] = pref[i - 1] * r ;
    }
    for(query i : qr)
    {
//        for(int j = 1 ; j <= n ; j++)
//        {
//            cout << (i.t / pref[j]) * pref[j] - j << ' ' ;
//        }
//        cout << '\n' ;
        ll l1 = 0, r1 = n + 1, l2 = 0, r2 = n + 1 ;
        while(l1 + 1 < r1)
        {
            ll mid = (l1 + r1) >> 1, posmd = (i.t / pref[mid]) * pref[mid] - mid ;
            if(posmd <= i.r)r1 = mid ;
            else l1 = mid ;
        }
        while(l2 + 1 < r2)
        {
            ll mid = (l2 + r2) >> 1, posmd = (i.t / pref[mid]) * pref[mid] - mid ;
            if(posmd >= i.l)l2 = mid ;
            else r2 = mid ;
        }
        cout << l2 - r1 + 1 + (i.l <= i.t && i.t <= i.r) << '\n' ;
//        cout << "\n" ;
    }
    return 0 ;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 26928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 26928 KB Output isn't correct
2 Halted 0 ms 0 KB -