Submission #797896

#	Time	Username	Problem	Language	Result	Execution time	Memory
797896		vjudge1	Worst Reporter 3 (JOI18_worst_reporter3)	C++14	12 / 100	141 ms	28576 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 flag ;
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] ;
        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)
            flag = 1 ;
        q.ind = i ;
        qr.push_back(q) ;
    }
    if(n <= 1000 && q <= 1000 && !flag)
    {
        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 ;
            }
//            cout << tn << '\n' ;
            for(auto j : pep)
            {
//                cout << j.fi << ' ' ;
                if(i.l <= j.fi && j.fi <= i.r)
                    sum++ ;
            }
//            cout << "\n______________\n" ;
            ans[i.ind] = sum ;
        }
        for(ll i = 1 ; i <= q ; i++)
            cout << ans[i] << '\n' ;
    }
    return 0 ;
}

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