oj.uz

Submission #840902

# Submission time Handle Problem Language Result Execution time Memory
840902 2023-08-31T20:33:38 Z kwongweng Inspections (NOI23_inspections) C++17
77 / 100
 2000 ms 555840 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

const int mxnode = 2e7+1,N = 2e5+1;
vi L(N), R(N), val(mxnode,-1);
vector<ll> s(N), lf(mxnode), rg(mxnode), sm(mxnode);
ll mxN = 1e12;

int ndcnt = 1;
int new_node(){
    ndcnt++; return ndcnt;
}

void update(int v, ll tl, ll tr, ll pos, ll num){
    if (tl==tr){sm[v] += num; return;}
    ll tm = (tl+tr)/2;
    if (pos <= tm){
        if (!lf[v]) lf[v] = new_node();
        update(lf[v], tl, tm, pos, num);
    }else{
        if (!rg[v]) rg[v] = new_node();
        update(rg[v], tm+1, tr, pos, num);
    }
    sm[v] = sm[lf[v]] + sm[rg[v]];
    //cout<<v<<" "<<tl<<" "<<tr<<" "<<sm[v]<<"\n";
}

ll get(int v, ll tl, ll tr, ll l, ll r){
    if (tl==l && tr==r) return sm[v];
    if (l>r) return 0;
    ll tm = (tl+tr)/2;
    ll ans = 0;
    if (lf[v]) ans += get(lf[v], tl, tm, l, min(r,tm));
    if (rg[v]) ans += get(rg[v], tm+1, tr, max(l,tm+1), r);
    return ans;
}

void upd(int v, int tl, int tr, int l, int r, int ind){
    if (tl != tr && val[v] != -1){
        val[2*v]=val[2*v+1]=val[v];
    }
    if (l>r) return;
    if (tl==l && tr==r && (tl==tr || val[v] != -1)){
        if (val[v] != -1){
            ll num = s[ind-1] + (l-L[ind]) - s[val[v]-1] - (l-L[val[v]]);
            //cout<<val[v]<<" "<<ind<<" "<<num<<" "<<r-l+1<<"\n";
            update(1,0,mxN,num,r-l+1); 
        }
        val[v] = ind;
        return;
    }
    int tm = (tl+tr)/2;
    upd(2*v,tl,tm,l,min(r,tm),ind);
    upd(2*v+1,tm+1,tr,max(l,tm+1),r,ind);
    if (val[2*v] == val[2*v+1] && val[2*v] != -1) val[v]=val[2*v];
    else val[v]=-1;
}


int main(){
    int n, m, q; cin>>n>>m>>q;
    
    FOR(i,1,m+1){
        cin>>L[i]>>R[i];
        upd(1,1,n,L[i],R[i],i);
        s[i]=s[i-1] + (R[i]-L[i]+1);
    }
    //cout<<ndcnt<<"\n";
    while (q--){
        ll S; cin>>S;
        cout<<get(1,0,mxN,S+1, mxN)<<" ";
    }
    cout<< "\n";
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 551332 KB Output is correct
2 Correct 158 ms 551300 KB Output is correct
3 Correct 157 ms 551348 KB Output is correct
4 Correct 158 ms 551300 KB Output is correct
5 Correct 160 ms 551372 KB Output is correct
6 Correct 157 ms 551364 KB Output is correct
7 Correct 158 ms 551376 KB Output is correct
8 Correct 159 ms 551376 KB Output is correct
9 Correct 172 ms 551356 KB Output is correct
10 Correct 157 ms 551280 KB Output is correct
11 Correct 159 ms 551288 KB Output is correct
12 Correct 155 ms 551268 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 551332 KB Output is correct
2 Correct 158 ms 551300 KB Output is correct
3 Correct 157 ms 551348 KB Output is correct
4 Correct 158 ms 551300 KB Output is correct
5 Correct 160 ms 551372 KB Output is correct
6 Correct 157 ms 551364 KB Output is correct
7 Correct 158 ms 551376 KB Output is correct
8 Correct 159 ms 551376 KB Output is correct
9 Correct 172 ms 551356 KB Output is correct
10 Correct 157 ms 551280 KB Output is correct
11 Correct 159 ms 551288 KB Output is correct
12 Correct 155 ms 551268 KB Output is correct
13 Correct 451 ms 552424 KB Output is correct
14 Correct 440 ms 552612 KB Output is correct
15 Correct 505 ms 553068 KB Output is correct
16 Correct 449 ms 552912 KB Output is correct
17 Correct 472 ms 552948 KB Output is correct
18 Correct 450 ms 553020 KB Output is correct
19 Correct 480 ms 552600 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 551384 KB Output is correct
2 Correct 163 ms 551296 KB Output is correct
3 Correct 472 ms 552796 KB Output is correct
4 Correct 454 ms 553896 KB Output is correct
5 Correct 1877 ms 555840 KB Output is correct
6 Correct 1775 ms 555236 KB Output is correct
7 Correct 1299 ms 555212 KB Output is correct
8 Correct 159 ms 551256 KB Output is correct
9 Correct 167 ms 551384 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 551332 KB Output is correct
2 Correct 158 ms 551300 KB Output is correct
3 Correct 157 ms 551348 KB Output is correct
4 Correct 158 ms 551300 KB Output is correct
5 Correct 160 ms 551372 KB Output is correct
6 Correct 157 ms 551364 KB Output is correct
7 Correct 158 ms 551376 KB Output is correct
8 Correct 159 ms 551376 KB Output is correct
9 Correct 172 ms 551356 KB Output is correct
10 Correct 157 ms 551280 KB Output is correct
11 Correct 159 ms 551288 KB Output is correct
12 Correct 155 ms 551268 KB Output is correct
13 Correct 451 ms 552424 KB Output is correct
14 Correct 440 ms 552612 KB Output is correct
15 Correct 505 ms 553068 KB Output is correct
16 Correct 449 ms 552912 KB Output is correct
17 Correct 472 ms 552948 KB Output is correct
18 Correct 450 ms 553020 KB Output is correct
19 Correct 480 ms 552600 KB Output is correct
20 Correct 499 ms 554440 KB Output is correct
21 Correct 448 ms 553188 KB Output is correct
22 Correct 487 ms 554180 KB Output is correct
23 Correct 455 ms 552860 KB Output is correct
24 Correct 447 ms 552620 KB Output is correct
25 Correct 460 ms 553800 KB Output is correct
26 Correct 499 ms 554008 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 551332 KB Output is correct
2 Correct 158 ms 551300 KB Output is correct
3 Correct 157 ms 551348 KB Output is correct
4 Correct 158 ms 551300 KB Output is correct
5 Correct 160 ms 551372 KB Output is correct
6 Correct 157 ms 551364 KB Output is correct
7 Correct 158 ms 551376 KB Output is correct
8 Correct 159 ms 551376 KB Output is correct
9 Correct 172 ms 551356 KB Output is correct
10 Correct 157 ms 551280 KB Output is correct
11 Correct 159 ms 551288 KB Output is correct
12 Correct 155 ms 551268 KB Output is correct
13 Correct 451 ms 552424 KB Output is correct
14 Correct 440 ms 552612 KB Output is correct
15 Correct 505 ms 553068 KB Output is correct
16 Correct 449 ms 552912 KB Output is correct
17 Correct 472 ms 552948 KB Output is correct
18 Correct 450 ms 553020 KB Output is correct
19 Correct 480 ms 552600 KB Output is correct
20 Correct 162 ms 551384 KB Output is correct
21 Correct 163 ms 551296 KB Output is correct
22 Correct 472 ms 552796 KB Output is correct
23 Correct 454 ms 553896 KB Output is correct
24 Correct 1877 ms 555840 KB Output is correct
25 Correct 1775 ms 555236 KB Output is correct
26 Correct 1299 ms 555212 KB Output is correct
27 Correct 159 ms 551256 KB Output is correct
28 Correct 167 ms 551384 KB Output is correct
29 Correct 499 ms 554440 KB Output is correct
30 Correct 448 ms 553188 KB Output is correct
31 Correct 487 ms 554180 KB Output is correct
32 Correct 455 ms 552860 KB Output is correct
33 Correct 447 ms 552620 KB Output is correct
34 Correct 460 ms 553800 KB Output is correct
35 Correct 499 ms 554008 KB Output is correct
36 Execution timed out 2072 ms 553024 KB Time limit exceeded
37 Halted 0 ms 0 KB -