oj.uz

Submission #855936

# Submission time Handle Problem Language Result Execution time Memory
855936 2023-10-02T10:35:09 Z Sorting Overtaking (IOI23_overtaking) C++17
100 / 100
 2193 ms 162288 KB 
#include "overtaking.h"
#include <algorithm>
#include <map>
#include <numeric>

using namespace std;
typedef long long ll;

const int N = 1000 + 3;

ll dp[N][N];
int n, m;
ll t[N], w[N], s[N], l, x;

map<ll, pair<vector<int>, int>> groups[N];
map<ll, pair<vector<int>, int>>::iterator iters[N][N];
ll time_at_sorting[N][N];

void reorder_buses(){
    int new_n = n;
    for(int i = 0; i < new_n; ++i){
        if(w[i] <= x){
            --new_n;
            swap(w[i], w[new_n]);
            swap(t[i], t[new_n]);
            --i;
        }
    }
    n = new_n;

    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);

    sort(perm.begin(), perm.end(), [&](int l, int r){
        if(w[l] != w[r])
            return w[l] < w[r];
        return t[l] < t[r];
    });

    static ll tmp[N];
    copy(t, t + n, tmp);
    for(int i = 0; i < n; ++i){
        t[i] = tmp[perm[i]];
    }
    copy(w, w + n, tmp);
    for(int i = 0; i < n; ++i){
        w[i] = tmp[perm[i]];
    }
}

void init_groups(){
    for(int i = 0; i < n; ++i){
        time_at_sorting[0][i] = t[i];
        groups[0][t[i]].first.push_back(i);
    }

    {
        int curr_cnt = 0;
        for(auto iter = groups[0].begin(); iter != groups[0].end(); ++iter){
            auto &[time, p] = *iter;
            for(int i = curr_cnt + 1; i <= curr_cnt + p.first.size(); ++i){
                iters[0][i] = iter;
            }
            curr_cnt += p.first.size();
            p.second = curr_cnt;
        }
    }

    for(int station = 1; station < m; ++station){
        vector<int> order;
        for(auto &[time, p]: groups[station - 1]){
            auto &v = p.first;
            for(int x: v){
                order.push_back(x);
            }
        }

        for(int i = 0; i < n; ++i){
            time_at_sorting[station][i] = time_at_sorting[station - 1][i] + (s[station] - s[station - 1]) * w[i];
        }

        ll max_so_far = 0;
        for(int x: order){
            max_so_far = max(max_so_far, time_at_sorting[station][x]);
            time_at_sorting[station][x] = max_so_far;
            groups[station][max_so_far].first.push_back(x);
        }

        int curr_cnt = 0;
        for(auto iter = groups[station].begin(); iter != groups[station].end(); ++iter){
            auto &[time, p] = *iter;

            auto &buses = p.first;
            auto &cnt = p.second;
            sort(buses.begin(), buses.end());

            for(int i = curr_cnt + 1; i <= curr_cnt + buses.size(); ++i){
                iters[station][i] = iter;
            }

            curr_cnt += buses.size();
            cnt = curr_cnt;
        }
    }
}

void init_buses(){
    reorder_buses();
    init_groups();
}

ll calc_time(int station, ll time){
    if(station == m - 1){
        return time;
    }

    int curr_cnt = 0;
    {
        auto curr_iter = groups[station].lower_bound(time);
        if(curr_iter == groups[station].begin()){
            curr_cnt = 0;
        }
        else{
            --curr_iter;
            curr_cnt = curr_iter->second.second;
        }
    }
    
    if(!curr_cnt){
        return (s[m - 1] - s[station]) * x + time;
    }

    int l = station + 1, r = m;
    while(l != r){
        int mid = (l + r) >> 1;
        
        ll time_at_mid = (s[mid] - s[station]) * x + time;

        auto iter = iters[mid][curr_cnt];
        int cnt = iter->second.second;
        ll time_at_iter = iter->first;

        if(time_at_iter >= time_at_mid){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }

    int next_station = l;
    if(next_station == m){
        return (s[m - 1] - s[station]) * x + time;
    }

    int prev_station = next_station - 1;
    ll time_at_prev_station = (s[prev_station] - s[station]) * x + time;

    auto iter = groups[prev_station].lower_bound(time_at_prev_station);
    if(iter == groups[prev_station].begin()){
        return (s[m - 1] - s[station]) * x + time;
    }

    --iter;
    int bus = iter->second.first.back();
    return dp[next_station][bus];
}

void calc_dp(){
    for(int station = m - 1; station >= 0; --station){
        if(station == m - 1){
            for(int i = 0; i < n; ++i){
                dp[station][i] = time_at_sorting[station][i];
            }
            continue;
        }

        for(int i = 0; i < n; ++i){
            dp[station][i] = calc_time(station, time_at_sorting[station][i]);
        }
    }
}

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    l = L, n = N, x = X, m = M;
    copy(T.begin(), T.end(), t);
    copy(W.begin(), W.end(), w);
    copy(S.begin(), S.end(), s);

    init_buses();
    calc_dp();
}

ll arrival_time(ll Y)
{
    return calc_time(0, Y);
}

Compilation message

overtaking.cpp: In function 'void init_groups()':
overtaking.cpp:61:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for(int i = curr_cnt + 1; i <= curr_cnt + p.first.size(); ++i){
      |                                       ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
overtaking.cpp:97:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for(int i = curr_cnt + 1; i <= curr_cnt + buses.size(); ++i){
      |                                       ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
overtaking.cpp: In function 'll calc_time(int, ll)':
overtaking.cpp:140:13: warning: unused variable 'cnt' [-Wunused-variable]
  140 |         int cnt = iter->second.second;
      |             ^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 11100 KB Output is correct
3 Correct 1 ms 11100 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 17244 KB Output is correct
7 Correct 3 ms 23388 KB Output is correct
8 Correct 3 ms 23644 KB Output is correct
9 Correct 3 ms 23644 KB Output is correct
10 Correct 4 ms 23644 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 3 ms 10996 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 11100 KB Output is correct
4 Correct 1 ms 11100 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 3 ms 12124 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 4 ms 12120 KB Output is correct
14 Correct 4 ms 12120 KB Output is correct
15 Correct 4 ms 12124 KB Output is correct
16 Correct 4 ms 12124 KB Output is correct
17 Correct 4 ms 12204 KB Output is correct
18 Correct 4 ms 12124 KB Output is correct
19 Correct 5 ms 12124 KB Output is correct
20 Correct 5 ms 12236 KB Output is correct
21 Correct 3 ms 11612 KB Output is correct
22 Correct 3 ms 11356 KB Output is correct
23 Correct 3 ms 11868 KB Output is correct
24 Correct 3 ms 11868 KB Output is correct
25 Correct 3 ms 11864 KB Output is correct
26 Correct 3 ms 11868 KB Output is correct
27 Correct 3 ms 11868 KB Output is correct
28 Correct 3 ms 11356 KB Output is correct
29 Correct 3 ms 11356 KB Output is correct
30 Correct 3 ms 11588 KB Output is correct
31 Correct 3 ms 11356 KB Output is correct
32 Correct 4 ms 12124 KB Output is correct
33 Correct 3 ms 12124 KB Output is correct
34 Correct 4 ms 12124 KB Output is correct
35 Correct 3 ms 12124 KB Output is correct
36 Correct 3 ms 12120 KB Output is correct
37 Correct 3 ms 12120 KB Output is correct
38 Correct 1 ms 10588 KB Output is correct
39 Correct 1 ms 10588 KB Output is correct
40 Correct 3 ms 12124 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 11100 KB Output is correct
4 Correct 1 ms 11100 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 17244 KB Output is correct
8 Correct 3 ms 23388 KB Output is correct
9 Correct 3 ms 23644 KB Output is correct
10 Correct 3 ms 23644 KB Output is correct
11 Correct 4 ms 23644 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 1 ms 10588 KB Output is correct
16 Correct 4 ms 12124 KB Output is correct
17 Correct 4 ms 12124 KB Output is correct
18 Correct 3 ms 12124 KB Output is correct
19 Correct 4 ms 12124 KB Output is correct
20 Correct 4 ms 12120 KB Output is correct
21 Correct 4 ms 12120 KB Output is correct
22 Correct 4 ms 12124 KB Output is correct
23 Correct 4 ms 12124 KB Output is correct
24 Correct 4 ms 12204 KB Output is correct
25 Correct 4 ms 12124 KB Output is correct
26 Correct 5 ms 12124 KB Output is correct
27 Correct 5 ms 12236 KB Output is correct
28 Correct 3 ms 11612 KB Output is correct
29 Correct 3 ms 11356 KB Output is correct
30 Correct 3 ms 11868 KB Output is correct
31 Correct 3 ms 11868 KB Output is correct
32 Correct 3 ms 11864 KB Output is correct
33 Correct 3 ms 11868 KB Output is correct
34 Correct 3 ms 11868 KB Output is correct
35 Correct 3 ms 11356 KB Output is correct
36 Correct 3 ms 11356 KB Output is correct
37 Correct 3 ms 11588 KB Output is correct
38 Correct 3 ms 11356 KB Output is correct
39 Correct 4 ms 12124 KB Output is correct
40 Correct 3 ms 12124 KB Output is correct
41 Correct 4 ms 12124 KB Output is correct
42 Correct 3 ms 12124 KB Output is correct
43 Correct 3 ms 12120 KB Output is correct
44 Correct 3 ms 12120 KB Output is correct
45 Correct 1 ms 10588 KB Output is correct
46 Correct 1 ms 10588 KB Output is correct
47 Correct 3 ms 12124 KB Output is correct
48 Correct 473 ms 128348 KB Output is correct
49 Correct 509 ms 128976 KB Output is correct
50 Correct 534 ms 131624 KB Output is correct
51 Correct 489 ms 128640 KB Output is correct
52 Correct 522 ms 128952 KB Output is correct
53 Correct 535 ms 128928 KB Output is correct
54 Correct 497 ms 128872 KB Output is correct
55 Correct 329 ms 92008 KB Output is correct
56 Correct 450 ms 128336 KB Output is correct
57 Correct 414 ms 121716 KB Output is correct
58 Correct 443 ms 129364 KB Output is correct
59 Correct 438 ms 128084 KB Output is correct
60 Correct 439 ms 128332 KB Output is correct
61 Correct 441 ms 129360 KB Output is correct
62 Correct 5 ms 23644 KB Output is correct
63 Correct 4 ms 10924 KB Output is correct
64 Correct 198 ms 75344 KB Output is correct
65 Correct 201 ms 70408 KB Output is correct
66 Correct 351 ms 123648 KB Output is correct
67 Correct 404 ms 125520 KB Output is correct
68 Correct 427 ms 125780 KB Output is correct
69 Correct 275 ms 133756 KB Output is correct
70 Correct 296 ms 133976 KB Output is correct
71 Correct 339 ms 133716 KB Output is correct
72 Correct 492 ms 133916 KB Output is correct
73 Correct 335 ms 133716 KB Output is correct
74 Correct 324 ms 133860 KB Output is correct
75 Correct 2 ms 10588 KB Output is correct
76 Correct 2 ms 10588 KB Output is correct
77 Correct 2 ms 10588 KB Output is correct
78 Correct 325 ms 133608 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 11100 KB Output is correct
4 Correct 1 ms 11100 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 17244 KB Output is correct
8 Correct 3 ms 23388 KB Output is correct
9 Correct 3 ms 23644 KB Output is correct
10 Correct 3 ms 23644 KB Output is correct
11 Correct 4 ms 23644 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 1 ms 10588 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 2 ms 10584 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 3 ms 10844 KB Output is correct
22 Correct 3 ms 10996 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10588 KB Output is correct
26 Correct 2 ms 10588 KB Output is correct
27 Correct 4 ms 12124 KB Output is correct
28 Correct 4 ms 12124 KB Output is correct
29 Correct 3 ms 12124 KB Output is correct
30 Correct 4 ms 12124 KB Output is correct
31 Correct 4 ms 12120 KB Output is correct
32 Correct 4 ms 12120 KB Output is correct
33 Correct 4 ms 12124 KB Output is correct
34 Correct 4 ms 12124 KB Output is correct
35 Correct 4 ms 12204 KB Output is correct
36 Correct 4 ms 12124 KB Output is correct
37 Correct 5 ms 12124 KB Output is correct
38 Correct 5 ms 12236 KB Output is correct
39 Correct 3 ms 11612 KB Output is correct
40 Correct 3 ms 11356 KB Output is correct
41 Correct 3 ms 11868 KB Output is correct
42 Correct 3 ms 11868 KB Output is correct
43 Correct 3 ms 11864 KB Output is correct
44 Correct 3 ms 11868 KB Output is correct
45 Correct 3 ms 11868 KB Output is correct
46 Correct 3 ms 11356 KB Output is correct
47 Correct 3 ms 11356 KB Output is correct
48 Correct 3 ms 11588 KB Output is correct
49 Correct 3 ms 11356 KB Output is correct
50 Correct 4 ms 12124 KB Output is correct
51 Correct 3 ms 12124 KB Output is correct
52 Correct 4 ms 12124 KB Output is correct
53 Correct 3 ms 12124 KB Output is correct
54 Correct 3 ms 12120 KB Output is correct
55 Correct 3 ms 12120 KB Output is correct
56 Correct 1 ms 10588 KB Output is correct
57 Correct 1 ms 10588 KB Output is correct
58 Correct 3 ms 12124 KB Output is correct
59 Correct 473 ms 128348 KB Output is correct
60 Correct 509 ms 128976 KB Output is correct
61 Correct 534 ms 131624 KB Output is correct
62 Correct 489 ms 128640 KB Output is correct
63 Correct 522 ms 128952 KB Output is correct
64 Correct 535 ms 128928 KB Output is correct
65 Correct 497 ms 128872 KB Output is correct
66 Correct 329 ms 92008 KB Output is correct
67 Correct 450 ms 128336 KB Output is correct
68 Correct 414 ms 121716 KB Output is correct
69 Correct 443 ms 129364 KB Output is correct
70 Correct 438 ms 128084 KB Output is correct
71 Correct 439 ms 128332 KB Output is correct
72 Correct 441 ms 129360 KB Output is correct
73 Correct 5 ms 23644 KB Output is correct
74 Correct 4 ms 10924 KB Output is correct
75 Correct 198 ms 75344 KB Output is correct
76 Correct 201 ms 70408 KB Output is correct
77 Correct 351 ms 123648 KB Output is correct
78 Correct 404 ms 125520 KB Output is correct
79 Correct 427 ms 125780 KB Output is correct
80 Correct 275 ms 133756 KB Output is correct
81 Correct 296 ms 133976 KB Output is correct
82 Correct 339 ms 133716 KB Output is correct
83 Correct 492 ms 133916 KB Output is correct
84 Correct 335 ms 133716 KB Output is correct
85 Correct 324 ms 133860 KB Output is correct
86 Correct 2 ms 10588 KB Output is correct
87 Correct 2 ms 10588 KB Output is correct
88 Correct 2 ms 10588 KB Output is correct
89 Correct 325 ms 133608 KB Output is correct
90 Correct 553 ms 129404 KB Output is correct
91 Correct 863 ms 154100 KB Output is correct
92 Correct 946 ms 156240 KB Output is correct
93 Correct 876 ms 154532 KB Output is correct
94 Correct 917 ms 154796 KB Output is correct
95 Correct 889 ms 154204 KB Output is correct
96 Correct 884 ms 154524 KB Output is correct
97 Correct 361 ms 94544 KB Output is correct
98 Correct 897 ms 153584 KB Output is correct
99 Correct 894 ms 147640 KB Output is correct
100 Correct 895 ms 153692 KB Output is correct
101 Correct 879 ms 152668 KB Output is correct
102 Correct 888 ms 153684 KB Output is correct
103 Correct 877 ms 153572 KB Output is correct
104 Correct 473 ms 98892 KB Output is correct
105 Correct 542 ms 95984 KB Output is correct
106 Correct 695 ms 154708 KB Output is correct
107 Correct 732 ms 152140 KB Output is correct
108 Correct 781 ms 153836 KB Output is correct
109 Correct 822 ms 152240 KB Output is correct
110 Correct 784 ms 153988 KB Output is correct
111 Correct 511 ms 159208 KB Output is correct
112 Correct 554 ms 159200 KB Output is correct
113 Correct 1210 ms 160384 KB Output is correct
114 Correct 2098 ms 161312 KB Output is correct
115 Correct 1091 ms 160824 KB Output is correct
116 Correct 630 ms 161012 KB Output is correct
117 Correct 163 ms 39308 KB Output is correct
118 Correct 165 ms 39248 KB Output is correct
119 Correct 165 ms 38596 KB Output is correct
120 Correct 176 ms 39284 KB Output is correct
121 Correct 164 ms 40272 KB Output is correct
122 Correct 1165 ms 156624 KB Output is correct
123 Correct 2193 ms 162124 KB Output is correct
124 Correct 2136 ms 162288 KB Output is correct
125 Correct 2193 ms 162132 KB Output is correct