oj.uz

Submission #797904

# Submission time Handle Problem Language Result Execution time Memory
797904 2023-07-30T05:52:12 Z vjudge1 Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 186 ms 30896 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 30824 KB Output is correct
2 Correct 175 ms 30768 KB Output is correct
3 Correct 179 ms 30896 KB Output is correct
4 Correct 172 ms 30760 KB Output is correct
5 Correct 183 ms 30844 KB Output is correct
6 Correct 186 ms 30868 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 30824 KB Output is correct
2 Correct 175 ms 30768 KB Output is correct
3 Correct 179 ms 30896 KB Output is correct
4 Correct 172 ms 30760 KB Output is correct
5 Correct 183 ms 30844 KB Output is correct
6 Correct 186 ms 30868 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Incorrect 148 ms 28524 KB Output isn't correct
14 Halted 0 ms 0 KB -