oj.uz

Submission #846504

# Submission time Handle Problem Language Result Execution time Memory
846504 2023-09-07T16:40:01 Z abcvuitunggio Overtaking (IOI23_overtaking) C++17
100 / 100
 2657 ms 919632 KB 
#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll INF=2e18;
vector <pii> st;
vector <int> le,ri;
vector <pair <pii, int>> v;
ll e[1001][1001],r[1001][1001],n,t[1001],w[1001],l,x,id;
void gen(){
    st.emplace_back(INF,INF);
    le.emplace_back(-1);
    ri.emplace_back(-1);
    id++;
}
void update(int node, ll l, ll r, ll u, ll v, pii p){
    if (l>v||r<u||l>r||u>v)
        return;
    if (l>=u&&r<=v){
        st[node]=min(st[node],p);
        return;
    }
    ll mid=(l+r)>>1;
    if (le[node]==-1){
        le[node]=id;
        gen();
    }
    update(le[node],l,mid,u,v,p);
    if (ri[node]==-1){
        ri[node]=id;
        gen();
    }
    update(ri[node],mid+1,r,u,v,p);
}
pii get(int node, ll l, ll r, ll i){
    pii p={INF,i};
    while (node!=-1){
        p=min(p,st[node]);
        ll mid=(l+r)>>1;
        if (mid>=i){
            r=mid;
            node=le[node];
        }
        else{
            l=mid+1;
            node=ri[node];
        }
    }
    return p;
}
void init(int L, int N, vector <ll> T, vector <int> W, int X, int m, vector <int> s){
    l=L;
    x=X;
    st.reserve(240LL*N*N);
    le.reserve(240LL*N*N);
    ri.reserve(240LL*N*N);
    for (int i=0;i<N;i++){
        if (W[i]>x){
            w[n]=W[i];
            e[n][0]=t[n]=T[i];
            n++;
        }
    }
    for (int i=1;i<m;i++){
        for (int j=0;j<n;j++)
            v.push_back({{e[j][i-1],w[j]},j});
        sort(v.begin(),v.end());
        ll mx=0;
        for (int it=0;it<v.size();it++){
            int j=v[it].second;
            mx=max(mx,e[j][i-1]+w[j]*(s[i]-s[i-1]));
            e[j][i]=mx;
            r[j][i-1]=min((it==v.size()-1?INF:e[v[it+1].second][i-1]),mx-x*(s[i]-s[i-1]));
        }
        v.clear();
    }
    gen();
    for (int i=m-1;i;i--){
        for (int j=0;j<n;j++)
            v.push_back({{e[j][i],w[j]},j});
        sort(v.begin(),v.end());
        for (auto p:v){
            int j=p.second;
            update(0,0,INF,e[j][i-1]+1+x*(l-s[i-1]),r[j][i-1]+x*(l-s[i-1]),{i,get(0,0,INF,e[j][i]+x*(l-s[i])).second});
        }
        v.clear();
    }
}
ll arrival_time(ll y){
    return get(0,0,INF,y+x*l).second;
}

Compilation message

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:70:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int it=0;it<v.size();it++){
      |                       ~~^~~~~~~~~
overtaking.cpp:74:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             r[j][i-1]=min((it==v.size()-1?INF:e[v[it+1].second][i-1]),mx-x*(s[i]-s[i-1]));
      |                            ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 2 ms 3160 KB Output is correct
7 Correct 2 ms 3144 KB Output is correct
8 Correct 3 ms 3688 KB Output is correct
9 Correct 3 ms 4196 KB Output is correct
10 Correct 3 ms 3656 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6744 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 4 ms 15704 KB Output is correct
7 Correct 4 ms 16220 KB Output is correct
8 Correct 4 ms 17752 KB Output is correct
9 Correct 4 ms 16216 KB Output is correct
10 Correct 3 ms 15452 KB Output is correct
11 Correct 3 ms 15704 KB Output is correct
12 Correct 4 ms 16220 KB Output is correct
13 Correct 1 ms 344 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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 1 ms 6744 KB Output is correct
9 Correct 11 ms 13656 KB Output is correct
10 Correct 12 ms 14936 KB Output is correct
11 Correct 12 ms 14428 KB Output is correct
12 Correct 12 ms 15964 KB Output is correct
13 Correct 11 ms 14680 KB Output is correct
14 Correct 12 ms 14168 KB Output is correct
15 Correct 12 ms 13660 KB Output is correct
16 Correct 12 ms 14940 KB Output is correct
17 Correct 11 ms 14680 KB Output is correct
18 Correct 11 ms 14424 KB Output is correct
19 Correct 11 ms 14144 KB Output is correct
20 Correct 12 ms 15192 KB Output is correct
21 Correct 9 ms 8536 KB Output is correct
22 Correct 6 ms 12120 KB Output is correct
23 Correct 8 ms 7000 KB Output is correct
24 Correct 12 ms 16808 KB Output is correct
25 Correct 13 ms 17240 KB Output is correct
26 Correct 13 ms 16216 KB Output is correct
27 Correct 12 ms 17244 KB Output is correct
28 Correct 11 ms 15448 KB Output is correct
29 Correct 10 ms 13400 KB Output is correct
30 Correct 11 ms 14936 KB Output is correct
31 Correct 13 ms 13144 KB Output is correct
32 Correct 7 ms 7256 KB Output is correct
33 Correct 7 ms 9560 KB Output is correct
34 Correct 9 ms 11312 KB Output is correct
35 Correct 11 ms 13400 KB Output is correct
36 Correct 9 ms 10328 KB Output is correct
37 Correct 9 ms 10076 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 6 ms 6748 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 2 ms 3160 KB Output is correct
8 Correct 2 ms 3144 KB Output is correct
9 Correct 3 ms 3688 KB Output is correct
10 Correct 3 ms 4196 KB Output is correct
11 Correct 3 ms 3656 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 1 ms 6744 KB Output is correct
15 Correct 1 ms 6744 KB Output is correct
16 Correct 11 ms 13656 KB Output is correct
17 Correct 12 ms 14936 KB Output is correct
18 Correct 12 ms 14428 KB Output is correct
19 Correct 12 ms 15964 KB Output is correct
20 Correct 11 ms 14680 KB Output is correct
21 Correct 12 ms 14168 KB Output is correct
22 Correct 12 ms 13660 KB Output is correct
23 Correct 12 ms 14940 KB Output is correct
24 Correct 11 ms 14680 KB Output is correct
25 Correct 11 ms 14424 KB Output is correct
26 Correct 11 ms 14144 KB Output is correct
27 Correct 12 ms 15192 KB Output is correct
28 Correct 9 ms 8536 KB Output is correct
29 Correct 6 ms 12120 KB Output is correct
30 Correct 8 ms 7000 KB Output is correct
31 Correct 12 ms 16808 KB Output is correct
32 Correct 13 ms 17240 KB Output is correct
33 Correct 13 ms 16216 KB Output is correct
34 Correct 12 ms 17244 KB Output is correct
35 Correct 11 ms 15448 KB Output is correct
36 Correct 10 ms 13400 KB Output is correct
37 Correct 11 ms 14936 KB Output is correct
38 Correct 13 ms 13144 KB Output is correct
39 Correct 7 ms 7256 KB Output is correct
40 Correct 7 ms 9560 KB Output is correct
41 Correct 9 ms 11312 KB Output is correct
42 Correct 11 ms 13400 KB Output is correct
43 Correct 9 ms 10328 KB Output is correct
44 Correct 9 ms 10076 KB Output is correct
45 Correct 0 ms 344 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 6 ms 6748 KB Output is correct
48 Correct 1270 ms 154448 KB Output is correct
49 Correct 1430 ms 335144 KB Output is correct
50 Correct 1435 ms 317652 KB Output is correct
51 Correct 1438 ms 350544 KB Output is correct
52 Correct 1413 ms 334928 KB Output is correct
53 Correct 1444 ms 336588 KB Output is correct
54 Correct 1435 ms 350956 KB Output is correct
55 Correct 815 ms 147536 KB Output is correct
56 Correct 1264 ms 342596 KB Output is correct
57 Correct 1288 ms 413560 KB Output is correct
58 Correct 1328 ms 372692 KB Output is correct
59 Correct 1314 ms 331488 KB Output is correct
60 Correct 1265 ms 343488 KB Output is correct
61 Correct 1332 ms 371504 KB Output is correct
62 Correct 4 ms 4196 KB Output is correct
63 Correct 5 ms 16472 KB Output is correct
64 Correct 642 ms 139600 KB Output is correct
65 Correct 763 ms 225020 KB Output is correct
66 Correct 1010 ms 22864 KB Output is correct
67 Correct 2095 ms 820124 KB Output is correct
68 Correct 2041 ms 874064 KB Output is correct
69 Correct 726 ms 68628 KB Output is correct
70 Correct 727 ms 96588 KB Output is correct
71 Correct 827 ms 264956 KB Output is correct
72 Correct 1059 ms 455448 KB Output is correct
73 Correct 866 ms 298200 KB Output is correct
74 Correct 890 ms 297352 KB Output is correct
75 Correct 1 ms 600 KB Output is correct
76 Correct 1 ms 600 KB Output is correct
77 Correct 1 ms 600 KB Output is correct
78 Correct 660 ms 43680 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 2 ms 3160 KB Output is correct
8 Correct 2 ms 3144 KB Output is correct
9 Correct 3 ms 3688 KB Output is correct
10 Correct 3 ms 4196 KB Output is correct
11 Correct 3 ms 3656 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 1 ms 6744 KB Output is correct
15 Correct 1 ms 6744 KB Output is correct
16 Correct 1 ms 6744 KB Output is correct
17 Correct 3 ms 11096 KB Output is correct
18 Correct 4 ms 15704 KB Output is correct
19 Correct 4 ms 16220 KB Output is correct
20 Correct 4 ms 17752 KB Output is correct
21 Correct 4 ms 16216 KB Output is correct
22 Correct 3 ms 15452 KB Output is correct
23 Correct 3 ms 15704 KB Output is correct
24 Correct 4 ms 16220 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 11 ms 13656 KB Output is correct
28 Correct 12 ms 14936 KB Output is correct
29 Correct 12 ms 14428 KB Output is correct
30 Correct 12 ms 15964 KB Output is correct
31 Correct 11 ms 14680 KB Output is correct
32 Correct 12 ms 14168 KB Output is correct
33 Correct 12 ms 13660 KB Output is correct
34 Correct 12 ms 14940 KB Output is correct
35 Correct 11 ms 14680 KB Output is correct
36 Correct 11 ms 14424 KB Output is correct
37 Correct 11 ms 14144 KB Output is correct
38 Correct 12 ms 15192 KB Output is correct
39 Correct 9 ms 8536 KB Output is correct
40 Correct 6 ms 12120 KB Output is correct
41 Correct 8 ms 7000 KB Output is correct
42 Correct 12 ms 16808 KB Output is correct
43 Correct 13 ms 17240 KB Output is correct
44 Correct 13 ms 16216 KB Output is correct
45 Correct 12 ms 17244 KB Output is correct
46 Correct 11 ms 15448 KB Output is correct
47 Correct 10 ms 13400 KB Output is correct
48 Correct 11 ms 14936 KB Output is correct
49 Correct 13 ms 13144 KB Output is correct
50 Correct 7 ms 7256 KB Output is correct
51 Correct 7 ms 9560 KB Output is correct
52 Correct 9 ms 11312 KB Output is correct
53 Correct 11 ms 13400 KB Output is correct
54 Correct 9 ms 10328 KB Output is correct
55 Correct 9 ms 10076 KB Output is correct
56 Correct 0 ms 344 KB Output is correct
57 Correct 1 ms 344 KB Output is correct
58 Correct 6 ms 6748 KB Output is correct
59 Correct 1270 ms 154448 KB Output is correct
60 Correct 1430 ms 335144 KB Output is correct
61 Correct 1435 ms 317652 KB Output is correct
62 Correct 1438 ms 350544 KB Output is correct
63 Correct 1413 ms 334928 KB Output is correct
64 Correct 1444 ms 336588 KB Output is correct
65 Correct 1435 ms 350956 KB Output is correct
66 Correct 815 ms 147536 KB Output is correct
67 Correct 1264 ms 342596 KB Output is correct
68 Correct 1288 ms 413560 KB Output is correct
69 Correct 1328 ms 372692 KB Output is correct
70 Correct 1314 ms 331488 KB Output is correct
71 Correct 1265 ms 343488 KB Output is correct
72 Correct 1332 ms 371504 KB Output is correct
73 Correct 4 ms 4196 KB Output is correct
74 Correct 5 ms 16472 KB Output is correct
75 Correct 642 ms 139600 KB Output is correct
76 Correct 763 ms 225020 KB Output is correct
77 Correct 1010 ms 22864 KB Output is correct
78 Correct 2095 ms 820124 KB Output is correct
79 Correct 2041 ms 874064 KB Output is correct
80 Correct 726 ms 68628 KB Output is correct
81 Correct 727 ms 96588 KB Output is correct
82 Correct 827 ms 264956 KB Output is correct
83 Correct 1059 ms 455448 KB Output is correct
84 Correct 866 ms 298200 KB Output is correct
85 Correct 890 ms 297352 KB Output is correct
86 Correct 1 ms 600 KB Output is correct
87 Correct 1 ms 600 KB Output is correct
88 Correct 1 ms 600 KB Output is correct
89 Correct 660 ms 43680 KB Output is correct
90 Correct 1325 ms 155632 KB Output is correct
91 Correct 1876 ms 363176 KB Output is correct
92 Correct 1870 ms 342200 KB Output is correct
93 Correct 1918 ms 379220 KB Output is correct
94 Correct 1891 ms 365132 KB Output is correct
95 Correct 1846 ms 363620 KB Output is correct
96 Correct 1860 ms 380572 KB Output is correct
97 Correct 878 ms 152656 KB Output is correct
98 Correct 1755 ms 368232 KB Output is correct
99 Correct 1792 ms 439968 KB Output is correct
100 Correct 1823 ms 393732 KB Output is correct
101 Correct 1771 ms 354896 KB Output is correct
102 Correct 1740 ms 370040 KB Output is correct
103 Correct 1776 ms 396824 KB Output is correct
104 Correct 1101 ms 173572 KB Output is correct
105 Correct 1514 ms 333680 KB Output is correct
106 Correct 1420 ms 57496 KB Output is correct
107 Correct 2356 ms 775156 KB Output is correct
108 Correct 2573 ms 857604 KB Output is correct
109 Correct 2608 ms 896132 KB Output is correct
110 Correct 2657 ms 919632 KB Output is correct
111 Correct 990 ms 93776 KB Output is correct
112 Correct 1010 ms 121592 KB Output is correct
113 Correct 1454 ms 333132 KB Output is correct
114 Correct 2054 ms 487828 KB Output is correct
115 Correct 1334 ms 281168 KB Output is correct
116 Correct 1207 ms 308304 KB Output is correct
117 Correct 172 ms 29008 KB Output is correct
118 Correct 171 ms 29008 KB Output is correct
119 Correct 166 ms 27920 KB Output is correct
120 Correct 173 ms 29008 KB Output is correct
121 Correct 172 ms 29776 KB Output is correct
122 Correct 1031 ms 64852 KB Output is correct
123 Correct 2205 ms 487436 KB Output is correct
124 Correct 2153 ms 487712 KB Output is correct
125 Correct 2206 ms 486472 KB Output is correct