oj.uz

Submission #911643

# Submission time Handle Problem Language Result Execution time Memory
911643 2024-01-19T04:25:16 Z marvinthang Overtaking (IOI23_overtaking) C++17
100 / 100
 1084 ms 94572 KB 
/*************************************
*    author: marvinthang             *
*    created: 19.01.2024 10:11:16    *
*************************************/

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b)  { return a < b ? a = b, true : false; }

// end of template

int n;
vector <long long> cx, st;
long long add;

void init(int L, int N, vector <long long> T, vector <int> W, int X, int M, vector <int> S) {
    add = 1LL * X * L;
    vector <pair <long long, int>> buses;
    REP(i, N) buses.emplace_back(T[i], W[i]);
    vector <vector <pair <long long, long long>>> lines(M - 1);
    REP(t, M - 1) {
        sort(ALL(buses));
        int dist = S[t + 1] - S[t];
        REP(i, N) {
            long long nxt = buses[i].fi + 1LL * buses[i].se * dist;
            if (i && nxt <= buses[i - 1].fi) nxt = buses[i - 1].fi;
            else {
                long long tl = buses[i].fi - 1LL * X * S[t] + 1;
                long long tr = nxt - 1LL * X * S[t + 1];
                if (tl >= 0 && tl < tr) {
                    lines[t].emplace_back(tl, tr);
                    cx.push_back(tl);
                    cx.push_back(tr);
                }
            }
            buses[i].fi = nxt;
        }
    }
    sort(ALL(cx));
    cx.erase(unique(ALL(cx)), cx.end());
    n = cx.size();
    st.resize(2 * n);
    REP(i, n) st[i + n] = cx[i];
    REPD(t, M - 1) {
        for (auto &[l, r]: lines[t]) {
            int tl = lower_bound(ALL(cx), l) - cx.begin();
            int tr = lower_bound(ALL(cx), r) - cx.begin();
            if (tl < tr) {
                long long val = 0;
                for (int i = tr + n; i; i >>= 1) maximize(val, st[i]);
                for (tl += n, tr += n; tl < tr; tl >>= 1, tr >>= 1) {
                    if (tl & 1) maximize(st[tl++], val);
                    if (tr & 1) maximize(st[--tr], val);
                }
            }
        }
    }
    FOR(i, 1, n) if (st[i]) {
        maximize(st[i << 1], st[i]);
        maximize(st[i << 1 | 1], st[i]);
    }
}

long long arrival_time(long long Y) {
    if (cx.empty() || Y < cx[0]) return Y + add;
    return add + max(Y, st[upper_bound(ALL(cx), Y) - cx.begin() - 1 + n]);
    return 0;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 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 344 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 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 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 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct

Subtask #3
20.0 / 20.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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 4 ms 980 KB Output is correct
10 Correct 4 ms 984 KB Output is correct
11 Correct 4 ms 1140 KB Output is correct
12 Correct 4 ms 984 KB Output is correct
13 Correct 4 ms 984 KB Output is correct
14 Correct 4 ms 984 KB Output is correct
15 Correct 4 ms 984 KB Output is correct
16 Correct 4 ms 980 KB Output is correct
17 Correct 5 ms 984 KB Output is correct
18 Correct 4 ms 980 KB Output is correct
19 Correct 4 ms 984 KB Output is correct
20 Correct 4 ms 984 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 3 ms 604 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 4 ms 860 KB Output is correct
25 Correct 4 ms 856 KB Output is correct
26 Correct 3 ms 856 KB Output is correct
27 Correct 3 ms 860 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 2 ms 860 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 1 ms 436 KB Output is correct
33 Correct 3 ms 860 KB Output is correct
34 Correct 3 ms 984 KB Output is correct
35 Correct 3 ms 1132 KB Output is correct
36 Correct 4 ms 984 KB Output is correct
37 Correct 3 ms 984 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 2 ms 604 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 0 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 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 4 ms 980 KB Output is correct
17 Correct 4 ms 984 KB Output is correct
18 Correct 4 ms 1140 KB Output is correct
19 Correct 4 ms 984 KB Output is correct
20 Correct 4 ms 984 KB Output is correct
21 Correct 4 ms 984 KB Output is correct
22 Correct 4 ms 984 KB Output is correct
23 Correct 4 ms 980 KB Output is correct
24 Correct 5 ms 984 KB Output is correct
25 Correct 4 ms 980 KB Output is correct
26 Correct 4 ms 984 KB Output is correct
27 Correct 4 ms 984 KB Output is correct
28 Correct 2 ms 600 KB Output is correct
29 Correct 3 ms 604 KB Output is correct
30 Correct 2 ms 604 KB Output is correct
31 Correct 4 ms 860 KB Output is correct
32 Correct 4 ms 856 KB Output is correct
33 Correct 3 ms 856 KB Output is correct
34 Correct 3 ms 860 KB Output is correct
35 Correct 2 ms 860 KB Output is correct
36 Correct 2 ms 604 KB Output is correct
37 Correct 2 ms 860 KB Output is correct
38 Correct 2 ms 860 KB Output is correct
39 Correct 1 ms 436 KB Output is correct
40 Correct 3 ms 860 KB Output is correct
41 Correct 3 ms 984 KB Output is correct
42 Correct 3 ms 1132 KB Output is correct
43 Correct 4 ms 984 KB Output is correct
44 Correct 3 ms 984 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 1 ms 348 KB Output is correct
47 Correct 2 ms 604 KB Output is correct
48 Correct 786 ms 58392 KB Output is correct
49 Correct 659 ms 61164 KB Output is correct
50 Correct 649 ms 62796 KB Output is correct
51 Correct 614 ms 61772 KB Output is correct
52 Correct 682 ms 62600 KB Output is correct
53 Correct 652 ms 61696 KB Output is correct
54 Correct 660 ms 61096 KB Output is correct
55 Correct 334 ms 42920 KB Output is correct
56 Correct 481 ms 61764 KB Output is correct
57 Correct 514 ms 58212 KB Output is correct
58 Correct 507 ms 62296 KB Output is correct
59 Correct 543 ms 61540 KB Output is correct
60 Correct 500 ms 61092 KB Output is correct
61 Correct 524 ms 62188 KB Output is correct
62 Correct 3 ms 600 KB Output is correct
63 Correct 2 ms 604 KB Output is correct
64 Correct 244 ms 30000 KB Output is correct
65 Correct 271 ms 29348 KB Output is correct
66 Correct 205 ms 30588 KB Output is correct
67 Correct 714 ms 58160 KB Output is correct
68 Correct 685 ms 60328 KB Output is correct
69 Correct 13 ms 604 KB Output is correct
70 Correct 355 ms 48932 KB Output is correct
71 Correct 478 ms 63596 KB Output is correct
72 Correct 465 ms 63580 KB Output is correct
73 Correct 484 ms 63592 KB Output is correct
74 Correct 475 ms 63604 KB Output is correct
75 Correct 20 ms 600 KB Output is correct
76 Correct 17 ms 624 KB Output is correct
77 Correct 12 ms 604 KB Output is correct
78 Correct 192 ms 24240 KB Output is correct

Subtask #5
35.0 / 35.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 0 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 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 4 ms 980 KB Output is correct
28 Correct 4 ms 984 KB Output is correct
29 Correct 4 ms 1140 KB Output is correct
30 Correct 4 ms 984 KB Output is correct
31 Correct 4 ms 984 KB Output is correct
32 Correct 4 ms 984 KB Output is correct
33 Correct 4 ms 984 KB Output is correct
34 Correct 4 ms 980 KB Output is correct
35 Correct 5 ms 984 KB Output is correct
36 Correct 4 ms 980 KB Output is correct
37 Correct 4 ms 984 KB Output is correct
38 Correct 4 ms 984 KB Output is correct
39 Correct 2 ms 600 KB Output is correct
40 Correct 3 ms 604 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 4 ms 860 KB Output is correct
43 Correct 4 ms 856 KB Output is correct
44 Correct 3 ms 856 KB Output is correct
45 Correct 3 ms 860 KB Output is correct
46 Correct 2 ms 860 KB Output is correct
47 Correct 2 ms 604 KB Output is correct
48 Correct 2 ms 860 KB Output is correct
49 Correct 2 ms 860 KB Output is correct
50 Correct 1 ms 436 KB Output is correct
51 Correct 3 ms 860 KB Output is correct
52 Correct 3 ms 984 KB Output is correct
53 Correct 3 ms 1132 KB Output is correct
54 Correct 4 ms 984 KB Output is correct
55 Correct 3 ms 984 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 1 ms 348 KB Output is correct
58 Correct 2 ms 604 KB Output is correct
59 Correct 786 ms 58392 KB Output is correct
60 Correct 659 ms 61164 KB Output is correct
61 Correct 649 ms 62796 KB Output is correct
62 Correct 614 ms 61772 KB Output is correct
63 Correct 682 ms 62600 KB Output is correct
64 Correct 652 ms 61696 KB Output is correct
65 Correct 660 ms 61096 KB Output is correct
66 Correct 334 ms 42920 KB Output is correct
67 Correct 481 ms 61764 KB Output is correct
68 Correct 514 ms 58212 KB Output is correct
69 Correct 507 ms 62296 KB Output is correct
70 Correct 543 ms 61540 KB Output is correct
71 Correct 500 ms 61092 KB Output is correct
72 Correct 524 ms 62188 KB Output is correct
73 Correct 3 ms 600 KB Output is correct
74 Correct 2 ms 604 KB Output is correct
75 Correct 244 ms 30000 KB Output is correct
76 Correct 271 ms 29348 KB Output is correct
77 Correct 205 ms 30588 KB Output is correct
78 Correct 714 ms 58160 KB Output is correct
79 Correct 685 ms 60328 KB Output is correct
80 Correct 13 ms 604 KB Output is correct
81 Correct 355 ms 48932 KB Output is correct
82 Correct 478 ms 63596 KB Output is correct
83 Correct 465 ms 63580 KB Output is correct
84 Correct 484 ms 63592 KB Output is correct
85 Correct 475 ms 63604 KB Output is correct
86 Correct 20 ms 600 KB Output is correct
87 Correct 17 ms 624 KB Output is correct
88 Correct 12 ms 604 KB Output is correct
89 Correct 192 ms 24240 KB Output is correct
90 Correct 850 ms 60332 KB Output is correct
91 Correct 1084 ms 88448 KB Output is correct
92 Correct 1044 ms 88424 KB Output is correct
93 Correct 939 ms 88464 KB Output is correct
94 Correct 958 ms 89776 KB Output is correct
95 Correct 913 ms 88176 KB Output is correct
96 Correct 909 ms 88300 KB Output is correct
97 Correct 413 ms 45596 KB Output is correct
98 Correct 848 ms 88284 KB Output is correct
99 Correct 757 ms 86412 KB Output is correct
100 Correct 785 ms 87980 KB Output is correct
101 Correct 848 ms 88100 KB Output is correct
102 Correct 812 ms 87916 KB Output is correct
103 Correct 869 ms 88084 KB Output is correct
104 Correct 532 ms 55336 KB Output is correct
105 Correct 629 ms 58468 KB Output is correct
106 Correct 464 ms 67096 KB Output is correct
107 Correct 924 ms 91056 KB Output is correct
108 Correct 1043 ms 93540 KB Output is correct
109 Correct 943 ms 93608 KB Output is correct
110 Correct 1016 ms 94572 KB Output is correct
111 Correct 170 ms 35668 KB Output is correct
112 Correct 668 ms 77332 KB Output is correct
113 Correct 801 ms 91852 KB Output is correct
114 Correct 901 ms 93204 KB Output is correct
115 Correct 832 ms 91048 KB Output is correct
116 Correct 754 ms 91936 KB Output is correct
117 Correct 196 ms 39352 KB Output is correct
118 Correct 193 ms 39352 KB Output is correct
119 Correct 180 ms 37460 KB Output is correct
120 Correct 183 ms 39504 KB Output is correct
121 Correct 188 ms 40528 KB Output is correct
122 Correct 488 ms 45544 KB Output is correct
123 Correct 1058 ms 93020 KB Output is correct
124 Correct 969 ms 93352 KB Output is correct
125 Correct 933 ms 93284 KB Output is correct