oj.uz

Submission #1118199

# Submission time Handle Problem Language Result Execution time Memory
1118199 2024-11-25T06:07:20 Z knot222 Inspections (NOI23_inspections) C++14
11 / 100
 28 ms 10732 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(NULL);
    int N,M,S;cin>>N>>M>>S;
    vector<pair<int,int>> ta(M);
    for (int i=0;i<M;i++) {
        cin>>ta[i].first >> ta[i].second;
    }
    
    priority_queue<pair<ll,int>> ss;
    vector<ll> ans(N);
    for (int i=0;i<S;i++) {
        ll t1;
        cin>>t1;
        ss.push(make_pair(t1,i));
    }
    priority_queue<pair<ll,int>> sl;
    //right -> {left, time}
    map<int,pair<int,ll>> range;
    ll tim = 0;
    int sum = 0;
    for (int i=0;i<M;i++) {
        auto it = range.lower_bound(ta[i].first);
        if (it!=range.end()) {
            int l = it->second.first;
            int r = it->first;
            int tt = it->second.second;
            if (l<ta[i].first) {
                range[ta[i].first-1] = {l, tt-(r-ta[i].first)-1};
                it->second.first = ta[i].first;
            }
        }
        while (it!=range.end() && it->first<=ta[i].second) {
            int l = it->second.first;
            int r = it->first;
            int tt = it->second.second;
            sum+=r-l+1;
            //sl.push(make_pair(tim-ta[i].first+r-tt, r-l+1));
            sl.push(make_pair(tim-ta[i].first+r-tt, r-l+1));
            it = range.erase(it);
        }
        if (it!=range.end()) {
            int l = it->second.first;
            int r = it->first;
            int tt = it->second.second;
            if (l<=ta[i].second) {
                sum+=ta[i].second-l+1;
                sl.push(make_pair(tim-ta[i].first+r-tt, ta[i].second-l+1));
                it->second.first = ta[i].second+1;
            }
        }
        tim+=ta[i].second-ta[i].first+1;
        range[ta[i].second] = make_pair(ta[i].first, tim);
    }
    sum=0;
    while (!ss.empty()) {
        while (!ss.empty() && !sl.empty() && ss.top().first<=sl.top().first) {
            sum+=sl.top().second;
            sl.pop();
        }
        ans[ss.top().second] = sum;
        ss.pop();
    }
    for (int i=0;i<S;i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}
/*
5 3 7                                       
1 3
3 5
2 3
0 1 2 3 4 5 6
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 504 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 472 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 352 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 504 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 472 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Runtime error 28 ms 10732 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 25 ms 10724 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 504 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 472 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Runtime error 28 ms 10732 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 504 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 472 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Runtime error 28 ms 10732 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -