oj.uz

Submission #832507

# Submission time Handle Problem Language Result Execution time Memory
832507 2023-08-21T10:58:30 Z _martynas Inspections (NOI23_inspections) C++11
29 / 100
 2000 ms 1048576 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>

using namespace std;

const int mxn = 2e5+5;

int n, m, q;
int l[mxn], r[mxn], ans[mxn];
long long s[mxn];

int main(int argc, char const *argv[]) {
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++) {
        cin >> l[i] >> r[i];
    }
    for(int i = 1; i <= q; i++) {
        cin >> s[i];
    }
    vector<int> order;
    for(int i = 1; i <= m; i++) {
        for(int j = l[i]; j <= r[i]; j++) {
            order.push_back(j);
        }
    }
    map<int, int> last, inc;
    for(int t = 0; t < (int)order.size(); t++) {
        if(last.find(order[t]) != last.end()) {
            inc[t-last[order[t]]-1]++;
        }
        last[order[t]] = t;
    }
    vector<int> dec_s(q); iota(dec_s.begin(), dec_s.end(), 1);
    sort(dec_s.begin(), dec_s.end(), [&](int i, int j) { return s[i] > s[j];});
    int sum = 0;
    auto it = inc.rbegin();
    for(int i = 0; i < q; i++) {
        int j = dec_s[i];
        while(it != inc.rend() && it->first >= s[j]) {
            sum += it->second;
            it++;
        }
        ans[j] = sum;
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << " ";
    cout << "\n";
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 267 ms 10208 KB Output is correct
14 Correct 80 ms 5524 KB Output is correct
15 Correct 355 ms 13564 KB Output is correct
16 Correct 356 ms 13516 KB Output is correct
17 Correct 103 ms 6252 KB Output is correct
18 Correct 347 ms 13376 KB Output is correct
19 Correct 283 ms 11404 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 KB Output is correct
2 Correct 2 ms 548 KB Output is correct
3 Correct 346 ms 11824 KB Output is correct
4 Runtime error 759 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 267 ms 10208 KB Output is correct
14 Correct 80 ms 5524 KB Output is correct
15 Correct 355 ms 13564 KB Output is correct
16 Correct 356 ms 13516 KB Output is correct
17 Correct 103 ms 6252 KB Output is correct
18 Correct 347 ms 13376 KB Output is correct
19 Correct 283 ms 11404 KB Output is correct
20 Execution timed out 2086 ms 528680 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 267 ms 10208 KB Output is correct
14 Correct 80 ms 5524 KB Output is correct
15 Correct 355 ms 13564 KB Output is correct
16 Correct 356 ms 13516 KB Output is correct
17 Correct 103 ms 6252 KB Output is correct
18 Correct 347 ms 13376 KB Output is correct
19 Correct 283 ms 11404 KB Output is correct
20 Correct 0 ms 216 KB Output is correct
21 Correct 2 ms 548 KB Output is correct
22 Correct 346 ms 11824 KB Output is correct
23 Runtime error 759 ms 1048576 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -