oj.uz

Submission #970955

# Submission time Handle Problem Language Result Execution time Memory
970955 2024-04-27T16:00:03 Z CSQ31 Inspections (NOI23_inspections) C++17
55 / 100
 137 ms 16524 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
//x - l_i + p_{i-1} - p_j + r_j - x
//(p_{i-1} - l_i) + (r_j - p_j) > s is the condition
//only r_j - p_j is important
struct range
{
    ll l,r,val = -1e18;
    range(){}
    range(ll _l,ll _r,ll _val){
        l = _l;
        r = _r;
        val = _val;
    }
    friend bool operator<(const range &a,const range &b){
        return b.r > a.r;
    }

};
set<range>s;
int main()
{
    owo
    int n,m,q;
    cin>>n>>m>>q;
    vector<PII>p(m),qs;
    vector<ll>pref(m,0);
    for(int i=0;i<m;i++){
        cin>>p[i].fi>>p[i].se;
        pref[i] = p[i].se - p[i].fi+1;
        if(i)pref[i]+=pref[i-1];
    }
    for(int i=0;i<q;i++){
        int x;
        cin>>x;
        qs.pb({x,i});
    }
    sort(all(qs));
    vector<ll>ans(q,0);
    s.insert(range(1,n,-1e18));

    for(int i=0;i<m;i++){
        ll l0 = p[i].fi;
        ll r0 = p[i].se;
        vector<range>add;
        add.pb(range(l0,r0,r0 - pref[i]));
        while(true){
            auto it = s.ub(range(0,l0-1,0)); //first guy with r >= l0
            if(it == s.end())break;
            if(it->l > r0)break;
            if(it->l < l0)add.pb(range(it->l,l0-1,it->val));
            if(it->r > r0)add.pb(range(r0+1,it->r,it->val));

            ll inter = min(r0,it->r) - max(l0,it->l)+1;
            ll gap = (i?pref[i-1]:0) - l0 + it->val + 1;
            //cout<<"gap "<<inter<<" "<<gap<<'\n';
            int idx = lb(all(qs),make_pair(gap,0LL)) - qs.begin()-1;
            if(idx>=0)ans[idx] += inter;
            s.erase(it);
        }
        for(auto x:add)s.insert(x);
        /*
        cout<<"at "<<i<<'\n';
        for(auto x:s){
            cout<<x.l<<" "<<x.r<<" "<<x.val<<'\n';
        }*/
    }
    for(int i=q-2;i>=0;i--)ans[i]+=ans[i+1];
    vector<ll>fin(q);
    for(int i=0;i<q;i++)fin[qs[i].se] = ans[i];
    for(int i=0;i<q;i++)cout<<fin[i]<<" ";
    cout<<'\n';




}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 44 ms 8628 KB Output is correct
14 Correct 42 ms 8376 KB Output is correct
15 Correct 43 ms 9404 KB Output is correct
16 Correct 50 ms 8820 KB Output is correct
17 Correct 45 ms 8932 KB Output is correct
18 Correct 43 ms 8464 KB Output is correct
19 Correct 44 ms 8724 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 43 ms 9096 KB Output is correct
4 Correct 47 ms 9144 KB Output is correct
5 Correct 137 ms 16524 KB Output is correct
6 Incorrect 76 ms 14020 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 44 ms 8628 KB Output is correct
14 Correct 42 ms 8376 KB Output is correct
15 Correct 43 ms 9404 KB Output is correct
16 Correct 50 ms 8820 KB Output is correct
17 Correct 45 ms 8932 KB Output is correct
18 Correct 43 ms 8464 KB Output is correct
19 Correct 44 ms 8724 KB Output is correct
20 Correct 53 ms 9744 KB Output is correct
21 Correct 43 ms 8884 KB Output is correct
22 Correct 43 ms 9912 KB Output is correct
23 Correct 44 ms 8888 KB Output is correct
24 Correct 42 ms 8636 KB Output is correct
25 Correct 45 ms 9220 KB Output is correct
26 Correct 44 ms 10516 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 44 ms 8628 KB Output is correct
14 Correct 42 ms 8376 KB Output is correct
15 Correct 43 ms 9404 KB Output is correct
16 Correct 50 ms 8820 KB Output is correct
17 Correct 45 ms 8932 KB Output is correct
18 Correct 43 ms 8464 KB Output is correct
19 Correct 44 ms 8724 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 43 ms 9096 KB Output is correct
23 Correct 47 ms 9144 KB Output is correct
24 Correct 137 ms 16524 KB Output is correct
25 Incorrect 76 ms 14020 KB Output isn't correct
26 Halted 0 ms 0 KB -