oj.uz

Submission #832651

# Submission time Handle Problem Language Result Execution time Memory
832651 2023-08-21T13:01:01 Z Liudas Inspections (NOI23_inspections) C++17
29 / 100
 2000 ms 809080 KB 
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int main(){
    int N, Q, M;
    cin >> N >> M >> Q;
    vector<vector<int>> arr(N);
    int day = 0;
    for(int i = 0; i < M; i ++){
        int a, b;
        cin >> a >> b;
        for(int j = a-1; j < b; j ++){
            arr[j].push_back(day++);
        }
    }
    //for(int i : arr[2])cout << i << endl;
    vector<pair<long long, long long>> pref;
    map<long long, long long> vals;
    for(int i = 0; i < N; i ++){
        for(int j = 1; j < (int)arr[i].size(); j ++){
            vals[arr[i][j] - arr[i][j-1] - 1]++;
        }
    }
    for(auto[l, r]: vals){
        pref.push_back({l,r});
    }
    pref.push_back({1e16,0});
    for(int i = (int)pref.size()-2; i >= 0; i --){
        pref[i].second += pref[i+1].second;
    }
    for(int i = 0; i < Q; i ++){
        long long q;
        cin >> q;
        int c = 0;
        c += (*lower_bound(pref.begin(), pref.end(), make_pair(q, 0ll))).second;
        cout << c << " ";
    }
    cout << endl;    
    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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 0 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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
13 Correct 327 ms 7904 KB Output is correct
14 Correct 274 ms 996 KB Output is correct
15 Correct 374 ms 12420 KB Output is correct
16 Correct 330 ms 11704 KB Output is correct
17 Correct 267 ms 1896 KB Output is correct
18 Correct 377 ms 11624 KB Output is correct
19 Correct 331 ms 8380 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 426 ms 12260 KB Output is correct
4 Execution timed out 2100 ms 809080 KB Time limit exceeded
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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
13 Correct 327 ms 7904 KB Output is correct
14 Correct 274 ms 996 KB Output is correct
15 Correct 374 ms 12420 KB Output is correct
16 Correct 330 ms 11704 KB Output is correct
17 Correct 267 ms 1896 KB Output is correct
18 Correct 377 ms 11624 KB Output is correct
19 Correct 331 ms 8380 KB Output is correct
20 Execution timed out 2093 ms 654980 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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
13 Correct 327 ms 7904 KB Output is correct
14 Correct 274 ms 996 KB Output is correct
15 Correct 374 ms 12420 KB Output is correct
16 Correct 330 ms 11704 KB Output is correct
17 Correct 267 ms 1896 KB Output is correct
18 Correct 377 ms 11624 KB Output is correct
19 Correct 331 ms 8380 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 426 ms 12260 KB Output is correct
23 Execution timed out 2100 ms 809080 KB Time limit exceeded
24 Halted 0 ms 0 KB -