| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1018962 |
2024-07-10T11:20:52 Z |
vjudge1 |
Snowball (JOI21_ho_t2) |
C++17 |
|
108 ms |
12324 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define tobit(n) bitset<20>(n) //выводит 20 элементов в битовую систему
#define all(v) (v).begin(), (v).end()
#define rtt(v, k) rotate(v.begin(), v.begin() + k, v.end()); //move k elements back
signed main(){
int n, q; cin >> n >> q;
vector<int> v(n); //крч позиции снежков
for(auto& u : v) cin >> u;
vector<int> w(q), mx(q, -LLONG_MAX), mn(q, LLONG_MAX);
for(int i = 0; i < q; i++){
cin >> w[i]; //сила ветра
if(i != 0){
w[i] += w[i - 1];
mn[i] = min(w[i], mn[i - 1]); mx[i] = max(w[i], mx[i - 1]);
} else mn[i] = mx[i] = w[i];
} //ар бир снежоктун весин определеяем
for(int i = 0; i < n; i++){
int a = 0, b = q, res = 0, x, y;
//бин поиск кийинки кун снежный комго отуш учун
x = v[i]; y = (i + 1 != n ? v[i + 1] : LLONG_MAX);
while(abs(a - b) != 1){
int c = (a + b) / 2;
if(mx[c] + x < mn[c] + y) a = c;
else b = c;
} if(a != -1){
int cur = 0, t = a;
for(int j = 0; j + t < q && j < 5; j++){
int curr = min((y + mn[a]), (x + mx[a]));
cur = max(cur, min(curr - x, abs(x - y)));
a++;
} res += cur;
} a = 0; b = q;
//бин посик мурунку кунго снежный комго отуш учун
x = v[i]; y = (i != 0 ? v[i - 1] : -LLONG_MAX);
while(abs(a - b) != 1){
int c = (a + b) / 2;
if(mn[c] + x > mx[c] + y) a = c;
else b = c;
} if(a != -1){
int cur = 0, t = a;
for(int j = 0; j + t < q && j < 5; j++){
int curr = max((x + mn[a]), (y + mx[a]));
cur = max(cur, min(x - curr, abs(x - y)));
a++;
} res += cur; //cout << "b: " << mx[a] << " " << cur << "\n";
} //снежоктордун акыркы вестери
cout << res << "\n";
}
}
// NEED TO FAST CIN && COUT //
const int fastIO = [](){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
return 0;
}();
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 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 |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 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 |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
344 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
17 ms |
7256 KB |
Output is correct |
| 21 |
Correct |
16 ms |
7000 KB |
Output is correct |
| 22 |
Correct |
16 ms |
6748 KB |
Output is correct |
| 23 |
Correct |
16 ms |
6744 KB |
Output is correct |
| 24 |
Correct |
24 ms |
6992 KB |
Output is correct |
| 25 |
Correct |
101 ms |
11860 KB |
Output is correct |
| 26 |
Correct |
102 ms |
11856 KB |
Output is correct |
| 27 |
Correct |
99 ms |
11572 KB |
Output is correct |
| 28 |
Correct |
105 ms |
11612 KB |
Output is correct |
| 29 |
Correct |
100 ms |
11084 KB |
Output is correct |
| 30 |
Correct |
104 ms |
10580 KB |
Output is correct |
| 31 |
Correct |
72 ms |
10064 KB |
Output is correct |
| 32 |
Correct |
67 ms |
10144 KB |
Output is correct |
| 33 |
Correct |
8 ms |
1624 KB |
Output is correct |
| 34 |
Correct |
103 ms |
12324 KB |
Output is correct |
| 35 |
Correct |
108 ms |
11600 KB |
Output is correct |
| 36 |
Correct |
99 ms |
11856 KB |
Output is correct |
| 37 |
Correct |
98 ms |
11600 KB |
Output is correct |
| 38 |
Correct |
97 ms |
11604 KB |
Output is correct |
| 39 |
Correct |
101 ms |
11600 KB |
Output is correct |
| 40 |
Correct |
75 ms |
11600 KB |
Output is correct |
| 41 |
Incorrect |
22 ms |
7760 KB |
Output isn't correct |
| 42 |
Halted |
0 ms |
0 KB |
- |
