#include <bits/stdc++.h>
using namespace std;
struct punct{
long long int c; // coordonata
long long int st; // cel mai din stanga colectat
long long int dr; // cel mai din dreapta colectat
long long int w; // the weight
};
int main(){
cin.tie(0);ios::sync_with_stdio(0);
//1.
int n, q;
//2.
cin >> n >> q;
punct v[n + 2];
//3.
for(int i = 1; i <= n; i++){
cin >> v[i].c;
v[i].st = v[i].c;
v[i].dr = v[i].c;
v[i].w = 0;
}
v[0].c = -1000000000000000000;
v[0].st = -1000000000000000000;
v[0].dr = -1000000000000000000;
v[n + 1].c = 1000000000000000000;
v[n + 1].st = 1000000000000000000;
v[n + 1].dr = 1000000000000000000;
cout << endl;
for(int ii = 0; ii < q; ii++){
long long int x; cin >> x;
//cout << "coord de inceput : ";
//for(int i = 1; i <= n; i++) cout << v[i].c << " ";
//cout << endl;
for(int i = 1; i <= n; i++){
long long int l = min(v[i].c, v[i].c + x);
long long int r = max(v[i].c, v[i].c + x);
if(x < 0){
if(l < v[i].st){
//cout << " -- > Adaugam la pozitia " << i << " " << v[i].st - max(l, v[i - 1].dr) << endl;
v[i].w += max(0ll, v[i].st - max(l, v[i - 1].dr));
v[i].st = l;
}
}else{
if(r > v[i].dr){
//cout << " -- > Adaugam la pozitia " << i << " " << min(r, v[i + 1].st) - v[i].dr << endl;
v[i].w += max(0ll, min(r, v[i + 1].st) - v[i].dr);
v[i].dr = r;
}
}
v[i].c += x;
}
}
for(int i = 1; i <= n; i++){
cout << v[i].w << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
7 ms |
348 KB |
Output is correct |
7 |
Correct |
6 ms |
344 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
5 ms |
344 KB |
Output is correct |
11 |
Correct |
5 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
6 ms |
348 KB |
Output is correct |
16 |
Correct |
6 ms |
348 KB |
Output is correct |
17 |
Correct |
7 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
4 ms |
552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
7 ms |
348 KB |
Output is correct |
7 |
Correct |
6 ms |
344 KB |
Output is correct |
8 |
Correct |
6 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
5 ms |
344 KB |
Output is correct |
11 |
Correct |
5 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
6 ms |
348 KB |
Output is correct |
16 |
Correct |
6 ms |
348 KB |
Output is correct |
17 |
Correct |
7 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
4 ms |
552 KB |
Output is correct |
20 |
Correct |
19 ms |
2368 KB |
Output is correct |
21 |
Correct |
22 ms |
2352 KB |
Output is correct |
22 |
Correct |
75 ms |
2356 KB |
Output is correct |
23 |
Correct |
576 ms |
2132 KB |
Output is correct |
24 |
Execution timed out |
2538 ms |
1808 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |