Submission #797904

#	Time	Username	Problem	Language	Result	Execution time	Memory
797904		vjudge1	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	19 / 100	186 ms	30896 KiB

worst_reporter3

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 5e5 ;
bool flag1, flag2 ;
ll n, q, tn, d[N + 1], ans[N + 1] ;
struct query
{
    ll t, l, r, ind ;
};
bool cmp(query q1, query q2)
{
    return (q1.t < q2.t) ;
}
vector<pair<ll, ll>> pep ;
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] ;
        if(d[i] > 1)flag1 = 1 ;
        pep.push_back({-i, d[i]}) ;
    }
    reverse(pep.begin(), pep.end()) ;
    pep.push_back({0, 0}) ;
    for(ll i = 1 ; i <= q ; i++)
    {
        query q ;
        cin >> q.t >> q.l >> q.r ;
        if(q.t > 1000)
            flag2 = 1 ;
        q.ind = i ;
        qr.push_back(q) ;
    }
    if(!flag1)
    {
        for(query q : qr)
        {
            ll l = q.t - n, r = q.t ;
            if(q.l <= l && r <= q.r)
            {
                cout << (r - l + 1) << '\n' ;
                continue ;
            }
            if(l <= q.l && q.r <= r)
            {
                cout << (q.r - q.l + 1) << '\n' ;
                continue ;
            }
            if(q.l <= l && l <= q.r && q.r <= r)
            {
                cout << (q.r - l + 1) << '\n' ;
                continue ;
            }
            if(l <= q.l && q.l <= r && r <= q.r)
            {
                cout << (r - q.l + 1) << '\n' ;
                continue ;
            }
            cout << "0\n" ;
        }
        return 0 ;
    }
    if(n <= 1000 && q <= 1000 && !flag2)
    {
        sort(qr.begin(), qr.end(), cmp) ;
        for(query i : qr)
        {
            ll sum = 0 ;
            while(tn < i.t)
            {
                tn++ ;
                pep[pep.size() - 1].fi = tn ;
                for(ll j = pep.size() - 2 ; j >= 0 ; j--)
                    if(pep[j + 1].fi - pep[j].fi > pep[j].se)
                        pep[j].fi = pep[j + 1].fi - 1 ;
            }
            for(auto j : pep)
            {
                if(i.l <= j.fi && j.fi <= i.r)
                    sum++ ;
            }
            ans[i.ind] = sum ;
        }
        for(ll i = 1 ; i <= q ; i++)
            cout << ans[i] << '\n' ;
    }
    return 0 ;
}

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