이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifdef __APPLE__
#include "debug.h"
//#define debug(...) 42
#else
#define debug(...) 42
#endif
void solve() {
int n, q;
cin >> n >> q;
vector<ll> x(n + 2), qs(q);
for (int i = 1; i <= n; ++i) {
cin >> x[i];
}
x[0] = -INFLL;
x[n + 1] = INFLL;
ll go_left = 0, go_right = 0, d = 0;
vector<ll> jumps_left(1, 0), jumps_right(1, 0);
vector<int> id_left(1, -1), id_right(1, -1);
for (int i = 0; i < q; ++i) {
cin >> qs[i];
d += qs[i];
if (d < go_left) {
go_left = d;
jumps_left.emplace_back(abs(d));
id_left.emplace_back(i);
}
if (d > go_right) {
go_right = d;
jumps_right.emplace_back(d);
id_right.emplace_back(i);
}
}
vector<ll> l(n + 2), r(n + 2);
for (int i = 0; i < n + 2; ++i) {
l[i] = x[i] + go_left;
r[i] = x[i] + go_right;
}
debug(go_left, go_right);
debug(l);
debug(r);
vector<ll> ans(n + 2, 0);
for (int i = 1; i < n + 2; ++i) {
if (r[i - 1] <= l[i] || (r[i - 1] == x[i - 1] && l[i] <= x[i - 1])) {
ans[i - 1] += go_right;
ans[i] += abs(go_left);
}
else {
ll lx = l[i], rx = min(r[i - 1], x[i]) + 1;
ans[i - 1] += (lx - x[i - 1]);
while (rx - lx > 1) {
ll mx = lx + (rx - lx) / 2;
int id1 = (int)(lower_bound(all(jumps_right), mx - x[i - 1]) - jumps_right.begin());
int id2 = (int)(lower_bound(all(jumps_left), x[i] - mx + 1) - jumps_left.begin());
int ev1 = id_right[id1], ev2 = id_left[id2];
if (ev1 < ev2) {
lx = mx;
}
else {
rx = mx;
}
}
ans[i - 1] += (lx - l[i]);
ans[i] += (x[i] - lx);
}
}
debug(ans);
for (int i = 1; i <= n; ++i) {
cout << ans[i] << en;
}
}
int main() {
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void solve()':
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
45 | #define debug(...) 42
| ^~
Main.cpp:79:5: note: in expansion of macro 'debug'
79 | debug(go_left, go_right);
| ^~~~~
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
45 | #define debug(...) 42
| ^~
Main.cpp:80:5: note: in expansion of macro 'debug'
80 | debug(l);
| ^~~~~
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
45 | #define debug(...) 42
| ^~
Main.cpp:81:5: note: in expansion of macro 'debug'
81 | debug(r);
| ^~~~~
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
45 | #define debug(...) 42
| ^~
Main.cpp:107:5: note: in expansion of macro 'debug'
107 | debug(ans);
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |