oj.uz

Submission #914150

# Submission time Handle Problem Language Result Execution time Memory
914150 2024-01-21T09:44:41 Z esomer Inspections (NOI23_inspections) C++17
100 / 100
 700 ms 44496 KB 
#include<bits/stdc++.h>
 
using namespace std;

#define int long long

vector<pair<int, int>> queries;
vector<long long> prefix;
vector<long long> substract;
vector<pair<int, int>> safety;
long long totalSum = 0;

long long sum(int l, int r){
    if(l > r) return 0;
    if(l > 0) return prefix[r] - prefix[l-1];
    else return prefix[r];
}

long long getDist(int i, int j, int ind){
    assert(i <= j);
    long long mid = sum(i+1, j-1);
    return mid + queries[i].second - ind + ind - queries[j].first;
}

void add(long long dist, int val){
    int lo = 0;
    int hi = (int)safety.size() - 1;
    int bst = (int)safety.size();
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(safety[mid].first > dist){
            bst = mid;
            hi = mid - 1;
        }else lo = mid + 1;
    }
    // cout << "add: dist " << dist << " val "<< val << " bst "<< bst << "\n";
    totalSum += val;
    substract[bst] += val;
}

void solve(){
    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> start(n), ends(n+1);
    queries.resize(m); prefix.resize(m);
    for(int i = 0; i < m; i++){
        int l, r; cin >> l >> r; l--; r--;
        start[l].push_back(i);
        ends[r+1].push_back(i);
        if(i == 0) prefix[i] = r - l + 1;
        else prefix[i] = prefix[i-1] + r - l + 1;
        queries[i] = {l, r};
    }
    safety.resize(q);
    substract.assign(q+1, 0);
    for(int i = 0; i < q; i++){
        int s; cin >> s;
        safety[i] = {s, i};
    }
    sort(safety.begin(), safety.end());
    set<pair<int, long long>> s;
    for(int i = 0; i < n; i++){
        for(int x : ends[i]){
            auto it = s.lower_bound({x, -1});
            pair<int, long long> p = *it;
            add(p.second, -(n-i));
            int prev = -1, nxt = -1;
            if(it != s.begin()){
                it--;
                prev = (*it).first;
            }
            s.erase(p);
            it = s.lower_bound({x, -1});
            if(it != s.end()){
                nxt = (*it).first;
            }
            if(nxt != -1){
                it = s.lower_bound({nxt, -1});
                add((*it).second, -(n-i));
                s.erase(it);
                if(prev == -1){
                    s.insert({nxt, -1});
                    add(-1, n-i);
                }else{
                    long long dist = getDist(prev, nxt, i);
                    s.insert({nxt, dist});
                    add(dist, n-i);
                }
            }
        }
        for(int x : start[i]){
            if(s.empty()){
                s.insert({x, -1});
                add(-1, n-i);
                continue;
            }
            auto it = s.lower_bound({x, -1});
            if(it == s.end()){
                it--;
                long long dist = getDist((*it).first, x, i);
                add(dist, n-i);
                s.insert({x, dist});
            }else if(it == s.begin()){
                int y = (*it).first;
                long long dist = getDist(x, y, i);
                add(dist, n-i);
                s.erase(it);
                s.insert({y, dist});
                s.insert({x, -1});
                add(-1, n-i);
            }else{
                pair<int, long long> tp = (*it);
                it--;
                pair<int, long long> btm = (*it);
                s.erase(tp);
                add(tp.second, -(n-i));
                long long distTpMe = getDist(x, tp.first, i);
                long long distMeBtm = getDist(btm.first, x, i);
                add(distTpMe, n-i);
                add(distMeBtm, n-i);
                s.insert({x, distMeBtm});
                s.insert({tp.first, distTpMe});
            }
        }
        // cout << "remove"<< endl;
    }
    vector<long long> ans(q);
    for(int i = 0; i < q; i++){
        totalSum -= substract[i];
        ans[safety[i].second] = totalSum;
    }
    for(long long& x : ans) cout << x << " ";
    cout << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // int tt; cin >> tt;
    int tt = 1;
    while(tt--) solve();
}

Subtask #1
11.0 / 11.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
18.0 / 18.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 55 ms 8908 KB Output is correct
14 Correct 42 ms 8660 KB Output is correct
15 Correct 48 ms 9016 KB Output is correct
16 Correct 43 ms 9136 KB Output is correct
17 Correct 43 ms 8760 KB Output is correct
18 Correct 43 ms 8788 KB Output is correct
19 Correct 50 ms 8848 KB Output is correct

Subtask #3
22.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 44 ms 8344 KB Output is correct
4 Correct 56 ms 18260 KB Output is correct
5 Correct 445 ms 41116 KB Output is correct
6 Correct 397 ms 40548 KB Output is correct
7 Correct 326 ms 32012 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #4
26.0 / 26.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 55 ms 8908 KB Output is correct
14 Correct 42 ms 8660 KB Output is correct
15 Correct 48 ms 9016 KB Output is correct
16 Correct 43 ms 9136 KB Output is correct
17 Correct 43 ms 8760 KB Output is correct
18 Correct 43 ms 8788 KB Output is correct
19 Correct 50 ms 8848 KB Output is correct
20 Correct 59 ms 19364 KB Output is correct
21 Correct 48 ms 18424 KB Output is correct
22 Correct 50 ms 19284 KB Output is correct
23 Correct 49 ms 18400 KB Output is correct
24 Correct 50 ms 18260 KB Output is correct
25 Correct 51 ms 18724 KB Output is correct
26 Correct 49 ms 18516 KB Output is correct

Subtask #5
23.0 / 23.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 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 55 ms 8908 KB Output is correct
14 Correct 42 ms 8660 KB Output is correct
15 Correct 48 ms 9016 KB Output is correct
16 Correct 43 ms 9136 KB Output is correct
17 Correct 43 ms 8760 KB Output is correct
18 Correct 43 ms 8788 KB Output is correct
19 Correct 50 ms 8848 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 44 ms 8344 KB Output is correct
23 Correct 56 ms 18260 KB Output is correct
24 Correct 445 ms 41116 KB Output is correct
25 Correct 397 ms 40548 KB Output is correct
26 Correct 326 ms 32012 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 59 ms 19364 KB Output is correct
30 Correct 48 ms 18424 KB Output is correct
31 Correct 50 ms 19284 KB Output is correct
32 Correct 49 ms 18400 KB Output is correct
33 Correct 50 ms 18260 KB Output is correct
34 Correct 51 ms 18724 KB Output is correct
35 Correct 49 ms 18516 KB Output is correct
36 Correct 700 ms 29852 KB Output is correct
37 Correct 669 ms 39268 KB Output is correct
38 Correct 490 ms 38744 KB Output is correct
39 Correct 246 ms 34132 KB Output is correct
40 Correct 429 ms 43596 KB Output is correct
41 Correct 249 ms 44124 KB Output is correct
42 Correct 236 ms 44496 KB Output is correct
43 Correct 237 ms 43348 KB Output is correct
44 Correct 226 ms 43352 KB Output is correct
45 Correct 475 ms 34328 KB Output is correct
46 Correct 409 ms 34524 KB Output is correct
47 Correct 277 ms 34644 KB Output is correct
48 Correct 554 ms 39716 KB Output is correct