#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 3e5+5;
const int mod = 1e9+7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct rect{
int x,y,r,c,i;
bool operator < (rect &R) {
if (x != R.x) return x < R.x;
return y < R.y;
}
};
bool isbeg[maxn], isend[maxn]; // for each rectangle, is it the beg or end?????
bool done[maxn];
ll dst[maxn];
pii s[maxn*4]; // minimum y position, index (in segment tree!!!!!)
void MO(int p, pii v, int o = 1, int l = 0, int r = maxn-1) {
if( l > p || r < p) return;
if( l == r) {
s[o] = v;
return;
}
int mid = (l+r)/2;
MO(p,v,o*2,l,mid); MO(p,v,o*2+1,mid+1,r);
s[o] = min(s[o*2],s[o*2+1]);
}
pii QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
if (l > R || r < L) return {inf, -1};
if (l >= L && r <= R) return s[o];
int mid = (l+r)/2;
return min(QU(L,R,o*2,l,mid), QU(L,R,o*2+1,mid+1,r));
}
void build(){
fill(s, s+maxn*4, pii{inf,-1});
}
ll get(vector<rect> v) {
for (rect &R : v) {
bug(R.x,R.y,R.r,R.c,R.i);
bug(isbeg[R.i]);
bug(isend[R.i]);
}
// sort(ALL(v));
memset(dst, 0x3f, sizeof dst);
int n = SZ(v);
priority_queue<pii, vector<pii>, greater<pii> >pq;
vector<pair<pii, int> > pts;
build();
for (rect &R : v) {
if (isbeg[R.i]) {
dst[R.i]=R.c;
pq.push({dst[R.i], R.i});
}else{
pts.pb({{R.x, R.y}, R.i});
}
}
sort(ALL(pts));
for (rect &R : v) {
if (isbeg[R.i]) continue;
int meat = lower_bound(ALL(pts), make_pair(make_pair(R.x, R.y), R.i)) - pts.begin();
MO(meat, {R.y, meat});
}
ll re = inf;
while (!pq.empty()) {
int me = pq.top().s; ll w = pq.top().f; pq.pop();
if (dst[me] != w) continue;
if (isend[me]) {
MN(re, dst[me]);
}
pair<pii, int> moo = make_pair(make_pair(v[me].x + v[me].r + 1, v[me].y + v[me].r + 1), 1000000);
int upto = upper_bound(ALL(pts), moo) - pts.begin() - 1;
pii hi = QU(0,upto);
while (hi.s != -1) {
if (hi.f > v[me].y + v[me].r + 1) break;
// bug(hi.s);
int who = pts[hi.s].s;
bug(me, who);
dst[who] = v[who].c + dst[me];
pq.push({dst[who], who});
MO(hi.s, {inf, -1});
hi = QU(0, upto);
}
}
if (re == inf) return -1;
return re;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
bug(1,2);
vector<rect> go;
int n,m; cin>>n>>m;
REP(i,m) {
int t,l,r,c; cin>>t>>l>>r>>c;
--l; --r;
isbeg[i] = l == 0;
isend[i] = r == n-1;
go.pb({l+t, l-t,r-l,c,i});
}
ll re =get(go);
cout<<re<<endl;
}
/*
10 5
1 8 10 30
1 1 6 50
2 7 7 100
3 5 7 11
2 8 8 11
7 6 10 4
4 1 3 1
*/
Compilation message
treatment.cpp: In function 'long long int get(std::vector<rect>)':
treatment.cpp:71:16: warning: unused variable 'R' [-Wunused-variable]
71 | for (rect &R : v) {
| ^
treatment.cpp:80:9: warning: unused variable 'n' [-Wunused-variable]
80 | int n = SZ(v);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
38060 KB |
Output is correct |
2 |
Correct |
127 ms |
38120 KB |
Output is correct |
3 |
Correct |
165 ms |
36436 KB |
Output is correct |
4 |
Correct |
147 ms |
36472 KB |
Output is correct |
5 |
Correct |
168 ms |
38460 KB |
Output is correct |
6 |
Correct |
177 ms |
38036 KB |
Output is correct |
7 |
Correct |
155 ms |
38016 KB |
Output is correct |
8 |
Correct |
92 ms |
38000 KB |
Output is correct |
9 |
Correct |
89 ms |
37960 KB |
Output is correct |
10 |
Correct |
99 ms |
37932 KB |
Output is correct |
11 |
Correct |
220 ms |
38696 KB |
Output is correct |
12 |
Correct |
188 ms |
38628 KB |
Output is correct |
13 |
Correct |
226 ms |
38120 KB |
Output is correct |
14 |
Correct |
200 ms |
38020 KB |
Output is correct |
15 |
Correct |
165 ms |
37928 KB |
Output is correct |
16 |
Correct |
176 ms |
37936 KB |
Output is correct |
17 |
Correct |
165 ms |
37256 KB |
Output is correct |
18 |
Correct |
191 ms |
38076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
21340 KB |
Output is correct |
2 |
Correct |
10 ms |
21460 KB |
Output is correct |
3 |
Correct |
10 ms |
21456 KB |
Output is correct |
4 |
Correct |
10 ms |
21460 KB |
Output is correct |
5 |
Correct |
9 ms |
21460 KB |
Output is correct |
6 |
Correct |
10 ms |
21444 KB |
Output is correct |
7 |
Correct |
12 ms |
21384 KB |
Output is correct |
8 |
Correct |
9 ms |
21460 KB |
Output is correct |
9 |
Correct |
9 ms |
21460 KB |
Output is correct |
10 |
Correct |
10 ms |
21492 KB |
Output is correct |
11 |
Correct |
10 ms |
21460 KB |
Output is correct |
12 |
Correct |
10 ms |
21384 KB |
Output is correct |
13 |
Correct |
11 ms |
21460 KB |
Output is correct |
14 |
Correct |
10 ms |
21460 KB |
Output is correct |
15 |
Correct |
9 ms |
21452 KB |
Output is correct |
16 |
Correct |
9 ms |
21452 KB |
Output is correct |
17 |
Correct |
9 ms |
21392 KB |
Output is correct |
18 |
Correct |
9 ms |
21460 KB |
Output is correct |
19 |
Correct |
9 ms |
21460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
21340 KB |
Output is correct |
2 |
Correct |
10 ms |
21460 KB |
Output is correct |
3 |
Correct |
10 ms |
21456 KB |
Output is correct |
4 |
Correct |
10 ms |
21460 KB |
Output is correct |
5 |
Correct |
9 ms |
21460 KB |
Output is correct |
6 |
Correct |
10 ms |
21444 KB |
Output is correct |
7 |
Correct |
12 ms |
21384 KB |
Output is correct |
8 |
Correct |
9 ms |
21460 KB |
Output is correct |
9 |
Correct |
9 ms |
21460 KB |
Output is correct |
10 |
Correct |
10 ms |
21492 KB |
Output is correct |
11 |
Correct |
10 ms |
21460 KB |
Output is correct |
12 |
Correct |
10 ms |
21384 KB |
Output is correct |
13 |
Correct |
11 ms |
21460 KB |
Output is correct |
14 |
Correct |
10 ms |
21460 KB |
Output is correct |
15 |
Correct |
9 ms |
21452 KB |
Output is correct |
16 |
Correct |
9 ms |
21452 KB |
Output is correct |
17 |
Correct |
9 ms |
21392 KB |
Output is correct |
18 |
Correct |
9 ms |
21460 KB |
Output is correct |
19 |
Correct |
9 ms |
21460 KB |
Output is correct |
20 |
Correct |
15 ms |
22160 KB |
Output is correct |
21 |
Correct |
17 ms |
22160 KB |
Output is correct |
22 |
Correct |
15 ms |
22288 KB |
Output is correct |
23 |
Correct |
15 ms |
22288 KB |
Output is correct |
24 |
Correct |
20 ms |
22360 KB |
Output is correct |
25 |
Correct |
22 ms |
22364 KB |
Output is correct |
26 |
Correct |
18 ms |
22296 KB |
Output is correct |
27 |
Correct |
16 ms |
22288 KB |
Output is correct |
28 |
Correct |
17 ms |
22288 KB |
Output is correct |
29 |
Correct |
17 ms |
22284 KB |
Output is correct |
30 |
Correct |
13 ms |
22320 KB |
Output is correct |
31 |
Correct |
14 ms |
22288 KB |
Output is correct |
32 |
Correct |
17 ms |
22380 KB |
Output is correct |
33 |
Correct |
16 ms |
22288 KB |
Output is correct |
34 |
Correct |
16 ms |
22288 KB |
Output is correct |
35 |
Correct |
17 ms |
22248 KB |
Output is correct |
36 |
Correct |
17 ms |
22288 KB |
Output is correct |
37 |
Correct |
16 ms |
22304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
38060 KB |
Output is correct |
2 |
Correct |
127 ms |
38120 KB |
Output is correct |
3 |
Correct |
165 ms |
36436 KB |
Output is correct |
4 |
Correct |
147 ms |
36472 KB |
Output is correct |
5 |
Correct |
168 ms |
38460 KB |
Output is correct |
6 |
Correct |
177 ms |
38036 KB |
Output is correct |
7 |
Correct |
155 ms |
38016 KB |
Output is correct |
8 |
Correct |
92 ms |
38000 KB |
Output is correct |
9 |
Correct |
89 ms |
37960 KB |
Output is correct |
10 |
Correct |
99 ms |
37932 KB |
Output is correct |
11 |
Correct |
220 ms |
38696 KB |
Output is correct |
12 |
Correct |
188 ms |
38628 KB |
Output is correct |
13 |
Correct |
226 ms |
38120 KB |
Output is correct |
14 |
Correct |
200 ms |
38020 KB |
Output is correct |
15 |
Correct |
165 ms |
37928 KB |
Output is correct |
16 |
Correct |
176 ms |
37936 KB |
Output is correct |
17 |
Correct |
165 ms |
37256 KB |
Output is correct |
18 |
Correct |
191 ms |
38076 KB |
Output is correct |
19 |
Correct |
10 ms |
21340 KB |
Output is correct |
20 |
Correct |
10 ms |
21460 KB |
Output is correct |
21 |
Correct |
10 ms |
21456 KB |
Output is correct |
22 |
Correct |
10 ms |
21460 KB |
Output is correct |
23 |
Correct |
9 ms |
21460 KB |
Output is correct |
24 |
Correct |
10 ms |
21444 KB |
Output is correct |
25 |
Correct |
12 ms |
21384 KB |
Output is correct |
26 |
Correct |
9 ms |
21460 KB |
Output is correct |
27 |
Correct |
9 ms |
21460 KB |
Output is correct |
28 |
Correct |
10 ms |
21492 KB |
Output is correct |
29 |
Correct |
10 ms |
21460 KB |
Output is correct |
30 |
Correct |
10 ms |
21384 KB |
Output is correct |
31 |
Correct |
11 ms |
21460 KB |
Output is correct |
32 |
Correct |
10 ms |
21460 KB |
Output is correct |
33 |
Correct |
9 ms |
21452 KB |
Output is correct |
34 |
Correct |
9 ms |
21452 KB |
Output is correct |
35 |
Correct |
9 ms |
21392 KB |
Output is correct |
36 |
Correct |
9 ms |
21460 KB |
Output is correct |
37 |
Correct |
9 ms |
21460 KB |
Output is correct |
38 |
Correct |
15 ms |
22160 KB |
Output is correct |
39 |
Correct |
17 ms |
22160 KB |
Output is correct |
40 |
Correct |
15 ms |
22288 KB |
Output is correct |
41 |
Correct |
15 ms |
22288 KB |
Output is correct |
42 |
Correct |
20 ms |
22360 KB |
Output is correct |
43 |
Correct |
22 ms |
22364 KB |
Output is correct |
44 |
Correct |
18 ms |
22296 KB |
Output is correct |
45 |
Correct |
16 ms |
22288 KB |
Output is correct |
46 |
Correct |
17 ms |
22288 KB |
Output is correct |
47 |
Correct |
17 ms |
22284 KB |
Output is correct |
48 |
Correct |
13 ms |
22320 KB |
Output is correct |
49 |
Correct |
14 ms |
22288 KB |
Output is correct |
50 |
Correct |
17 ms |
22380 KB |
Output is correct |
51 |
Correct |
16 ms |
22288 KB |
Output is correct |
52 |
Correct |
16 ms |
22288 KB |
Output is correct |
53 |
Correct |
17 ms |
22248 KB |
Output is correct |
54 |
Correct |
17 ms |
22288 KB |
Output is correct |
55 |
Correct |
16 ms |
22304 KB |
Output is correct |
56 |
Correct |
147 ms |
36772 KB |
Output is correct |
57 |
Correct |
153 ms |
37248 KB |
Output is correct |
58 |
Correct |
172 ms |
37176 KB |
Output is correct |
59 |
Correct |
173 ms |
37504 KB |
Output is correct |
60 |
Correct |
171 ms |
38328 KB |
Output is correct |
61 |
Correct |
191 ms |
37204 KB |
Output is correct |
62 |
Correct |
169 ms |
36944 KB |
Output is correct |
63 |
Correct |
155 ms |
38132 KB |
Output is correct |
64 |
Correct |
160 ms |
38116 KB |
Output is correct |
65 |
Correct |
174 ms |
38380 KB |
Output is correct |
66 |
Correct |
163 ms |
38368 KB |
Output is correct |
67 |
Correct |
234 ms |
38680 KB |
Output is correct |
68 |
Correct |
187 ms |
38732 KB |
Output is correct |
69 |
Correct |
162 ms |
38700 KB |
Output is correct |
70 |
Correct |
216 ms |
38776 KB |
Output is correct |
71 |
Correct |
185 ms |
38792 KB |
Output is correct |
72 |
Correct |
160 ms |
38800 KB |
Output is correct |
73 |
Correct |
204 ms |
38772 KB |
Output is correct |
74 |
Correct |
98 ms |
38764 KB |
Output is correct |
75 |
Correct |
90 ms |
38724 KB |
Output is correct |
76 |
Correct |
218 ms |
38972 KB |
Output is correct |
77 |
Correct |
223 ms |
39276 KB |
Output is correct |
78 |
Correct |
208 ms |
38460 KB |
Output is correct |
79 |
Correct |
232 ms |
38780 KB |
Output is correct |
80 |
Correct |
181 ms |
38388 KB |
Output is correct |
81 |
Correct |
129 ms |
38684 KB |
Output is correct |
82 |
Correct |
186 ms |
37600 KB |
Output is correct |
83 |
Correct |
195 ms |
37832 KB |
Output is correct |
84 |
Correct |
206 ms |
37904 KB |
Output is correct |
85 |
Correct |
155 ms |
38780 KB |
Output is correct |
86 |
Correct |
172 ms |
38704 KB |
Output is correct |
87 |
Correct |
171 ms |
38816 KB |
Output is correct |
88 |
Correct |
181 ms |
38800 KB |
Output is correct |
89 |
Correct |
169 ms |
38708 KB |
Output is correct |
90 |
Correct |
233 ms |
39300 KB |
Output is correct |
91 |
Correct |
190 ms |
38712 KB |
Output is correct |
92 |
Correct |
163 ms |
38784 KB |
Output is correct |
93 |
Correct |
243 ms |
38704 KB |
Output is correct |
94 |
Correct |
176 ms |
38708 KB |
Output is correct |
95 |
Correct |
190 ms |
38792 KB |
Output is correct |
96 |
Correct |
228 ms |
39232 KB |
Output is correct |
97 |
Correct |
222 ms |
39292 KB |
Output is correct |
98 |
Correct |
237 ms |
39308 KB |
Output is correct |
99 |
Correct |
243 ms |
39340 KB |
Output is correct |
100 |
Correct |
194 ms |
39000 KB |
Output is correct |
101 |
Correct |
242 ms |
39300 KB |
Output is correct |
102 |
Correct |
224 ms |
39556 KB |
Output is correct |
103 |
Correct |
199 ms |
38804 KB |
Output is correct |