제출 #586857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586857		TheEvilBird	Snowball (JOI21_ho_t2)	C++17	33 / 100	819 ms	20852 KiB

Main

#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);
      |     ^~~~~

• Subtask 1: 33 / 33
• Subtask 2: 0 / 67