RiseOJ는 solved.ac와 제휴 관계가 없습니다. 티어 아이콘 © solved.ac. solved.ac
포럼
A00009

알파카컵 1회: I - 알파카의 식사

Diamond I 다이아몬드 I
난이도
2s
시간 제한
1024MB
메모리 제한
0
맞았습니다!!
12
제출 수
0.0%
정답률
레이팅

의견: 1

설명

알파카들이 사는 목장은 일직선 구조이며, \(N\)개의 풀들이 있다.
각 풀의 위치는 \(x_1, x_2, \dots, x_N\)이다.
\(0\)일째 \(i\)번째 풀의 초기 길이는 \(a_i\)이며, 하루마다 \(b_i\)씩 자란다.
만일 알파카가 풀을 먹으면, 해당 풀의 길이만큼 만족도를 얻는다.
그러나 풀들 중에는 독초도 존재하는데, 독초를 먹을 경우 해당 풀의 길이만큼 만족도를 잃는다. 독초 여부는 \(p_i\)가 \(0\)이면 독초가 아니고, \(1\)이면 독초다.

목장에 사는 알파카중 하나인 경현이는 다음과 같은 \(Q\)개의 식사 계획을 세웠다.

  • l r t : \(t\)일째에 위치 \(l\)과 위치 \(r\) 사이에 존재하는 선분 하나를 잡아 선분 내에 있는 모든 풀을 먹는다. 이때 선분은 모든 풀을 먹을 때 최대의 만족도를 얻도록 한다. 선분 내에 풀이 하나도 존재하지 않아도 된다.

여러 개의 풀이 같은 위치에 존재할 수 있다. 선분이 어떤 위치를 포함한다면, 그 위치에 존재하는 모든 풀을 먹어야 하며, 같은 위치에 있는 풀들 중 일부만 골라 먹을 수는 없다.

경현이를 도와 각 계획에 대한 최대의 만족도를 구해보자!

제약

\(1 \le N, Q \le 250{,}000\)
\(1 \le a_i \le 10^9\)
\(0 \le b_i \le 1{,}000\)
\(1 \le x_i \le 10^9\)
\(p_i\)는 \(0\) 또는 \(1\)이다.
각 계획에 대해 \(1 \le l \le r \le 10^9\), \(0 \le t \le 10^9\)

입력 형식

첫째 줄에 \(N\), \(Q\)가 주어진다.
둘째 줄부터 \(N\)개의 줄에 \(x_i\), \(a_i\), \(b_i\), \(p_i\)가 주어진다.
그 다음 줄부터 \(Q\)개의 줄에 각 계획 \(l\), \(r\), \(t\)가 주어진다.

출력 형식

각 계획에 대한 최대의 만족도를 출력한다.

서브태스크
서브태스크점수설명

서브태스크 1

5점

\(N = 1\)

서브태스크 2

5점

\(Q = 1\)

서브태스크 3

5점

독초가 주어지지 않는다.

서브태스크 4

20점

\(1 \le N, Q \le 1{,}000\)

서브태스크 5

25점

모든 \(i\)에 대해 \(b_i = 0\)

서브태스크 6

40점

추가 제약 조건이 없다.

예제 1
입력
5 6
1 10 1 0
2 20 1 1
3 5 1 1
4 20 1 1
5 10 1 0
1 1000000000 0
1 1000000000 10
1 1000000000 1000000000
1 1 0
5 5 1000000000
2 4 0
출력
10
20
1000000010
10
1000000010
0
문제 정보

pythonprominhyeong 작성

출처 알파카컵 1회

대회 > 알파카컵 > 알파카컵 1회
태그
#자료 구조#좌표 압축#세그먼트 트리#컨벡스 헐 트릭 JudgeOriginal

해설

알파카컵 1회: I - 알파카의 식사

알파카컵 1회: I - 알파카의 식사

1. 문제 요약

일직선 위에 \(N\)개의 풀이 있습니다. \(i\)번째 풀은 위치 \(x_i\)에 있고, \(t\)일째의 길이는 \(a_i + b_i \cdot t\)입니다. 풀을 먹으면 그 길이만큼 만족도를 얻지만, 독초(\(p_i = 1\))를 먹으면 그 길이만큼 만족도를 잃습니다.

\(Q\)개의 쿼리 l r t가 주어지며, 각 쿼리는 \(t\)일째에 위치 구간 \([l, r]\) 안에서 연속한 부분 선분 \([L, R] \subseteq [l, r]\)을 하나 골라, 그 안에 있는 모든 풀을 먹었을 때의 최대 만족도를 묻습니다.

여기서 두 가지 미묘한 점을 정확히 짚고 넘어가야 합니다.

  • 같은 위치의 풀은 묶어서 처리한다. 선분이 어떤 위치를 포함하면 그 위치의 모든 풀을 반드시 먹어야 하고, 일부만 골라 먹을 수 없습니다. 따라서 위치별로 그 위치에 있는 풀들의 기여를 하나의 값으로 묶을 수 있습니다. 위치 \(pos\)의 \(t\)일째 가중치를
    $$ w(pos, t) = \sum_{x_i = pos} (p_i = 1 \,?\, -1 : +1)\cdot(a_i + b_i \cdot t) $$
    로 정의하면, 이 값은 \(t\)에 대한 1차 함수 \(A_{pos} + B_{pos}\cdot t\) 입니다(\(A_{pos} = \sum \pm a_i\), \(B_{pos} = \sum \pm b_i\)). 즉 같은 위치의 여러 풀은 하나의 위치 가중치로 합쳐집니다.

  • 빈 선분이 허용되어 답은 항상 \(0\) 이상이다. 선분 안에 풀이 하나도 없어도 되므로, 만족도가 음수가 될 바에는 아무것도 먹지 않으면 됩니다.

결국 각 쿼리는 다음과 같이 정리됩니다. 위치 좌표가 \([l, r]\)에 속하는 위치들을 위치 순서대로 나열한 배열에서, \(t\)일째 가중치 \(w(\cdot, t)\)에 대한 (빈 구간을 허용하는) 최대 연속 부분합(Maximum Subarray Sum)을 구하라. 위치 좌표와 \(t\)가 모두 최대 \(10^9\)이므로 좌표 압축이 필요하고, 가중치가 \(t\)에 대해 1차로 변한다는 점이 이 문제를 어렵게 만듭니다.

값의 범위에 유의해야 합니다. 한 풀의 길이는 \(a_i + b_i \cdot t \le 10^9 + 10^3 \cdot 10^9 \approx 10^{12}\)까지 커지고, 최대 \(2.5 \times 10^5\)개의 위치 가중치를 더하면 \(5 \times 10^{17}\) 규모가 되므로 반드시 64비트 정수(long long)를 사용해야 합니다.

2. [서브태스크 1]: \(N = 1\)

풀이 단 하나뿐인 경우입니다. 선분을 잡는다는 개념이 사라지고, "그 하나의 풀을 먹을지 말지"만 결정하면 됩니다.

  • 풀이: 유일한 풀의 위치 \(x\)가 쿼리 구간 \([l, r]\)에 포함되는지 확인합니다. 포함된다면 \(t\)일째 가중치 \(w = a + b\cdot t\)를 계산하되, 독초라면 부호를 뒤집습니다. 빈 선분이 허용되므로 답은 \(\max(0, w)\)입니다. 포함되지 않으면 답은 \(0\)입니다.

  • 시간 복잡도: 쿼리당 \(O(1)\), 전체 \(O(Q)\)입니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
int main() {
    fastio
    ll n, q; cin >> n >> q;
    ll x, a, b, p; cin >> x >> a >> b >> p;
    while (q--) {
        ll l, r, t; cin >> l >> r >> t;
        ll w = a + b * t;
        if (p) w = -w;
        ll ans = 0;
        if (l <= x && x <= r) ans = max(0LL, w);
        cout << ans << endl;
    }
    return 0;
}

3. [서브태스크 2]: \(Q = 1\)

쿼리가 단 하나뿐인 경우입니다. 시간 제한 안에서라면 그 한 번의 쿼리를 위해 \(O(N)\) 정도의 비용을 들여도 충분합니다.

  • 풀이: 주어진 \(t\)에 대해, 위치가 \([l, r]\)에 속하는 모든 풀의 가중치 \(\pm(a_i + b_i\cdot t)\)를 위치별로 합산합니다. 그 다음 위치를 좌표 순서대로 나열한 뒤, 빈 구간을 허용하는 카데인(Kadane) 알고리즘으로 최대 연속 부분합을 구합니다. 위치별 합산은 map(또는 정렬)으로 처리하면 자연스럽게 위치 순서가 보장됩니다.

  • 시간 복잡도: 쿼리당 \(O(N \log N)\), \(Q = 1\)이므로 전체 \(O(N \log N)\)입니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
int main() {
    fastio
    ll n, q; cin >> n >> q;
    vector<ll> x(n), a(n), b(n), p(n);
    for (ll i = 0; i < n; i++) cin >> x[i] >> a[i] >> b[i] >> p[i];
    while (q--) {
        ll l, r, t; cin >> l >> r >> t;
        map<ll, ll> w; // 위치 -> 가중치 합 (정렬된 순서)
        for (ll i = 0; i < n; i++) if (x[i] >= l && x[i] <= r) {
            ll val = a[i] + b[i] * t;
            if (p[i]) val = -val;
            w[x[i]] += val;
        }
        ll best = 0, cur = 0;
        for (auto& pr : w) {
            cur += pr.second;
            if (cur < 0) cur = 0;
            best = max(best, cur);
        }
        cout << best << endl;
    }
    return 0;
}

4. [서브태스크 3]: 독초가 주어지지 않는다.

모든 풀이 독초가 아니므로 모든 위치 가중치 \(w(pos, t) = A_{pos} + B_{pos}\cdot t\)가 항상 \(0\) 이상입니다(\(a_i \ge 1\), \(b_i \ge 0\)).

  • 풀이: 모든 값이 음이 아니므로, 어떤 위치를 더해도 합이 줄어들지 않습니다. 따라서 최대 연속 부분합은 단순히 구간 \([l, r]\) 안의 모든 위치 가중치의 합입니다. 위치 가중치는 \(t\)의 1차 함수이므로, 구간 합도 \((\sum A_{pos}) + (\sum B_{pos})\cdot t\)로 표현됩니다. 위치를 좌표 압축한 뒤 \(A\)와 \(B\) 각각의 누적합(prefix sum)을 만들어 두면, 각 쿼리는 이분 탐색으로 구간 경계를 찾아 \(O(\log N)\)에 처리됩니다.

  • 시간 복잡도: 전처리 \(O(N \log N)\), 쿼리당 \(O(\log N)\), 전체 \(O((N + Q)\log N)\)입니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
int main() {
    fastio
    ll n, q; cin >> n >> q;
    vector<ll> x(n), a(n), b(n), p(n);
    for (ll i = 0; i < n; i++) cin >> x[i] >> a[i] >> b[i] >> p[i];
    vector<ll> xs(x.begin(), x.end());
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    ll M = xs.size();
    vector<ll> A(M, 0), B(M, 0);
    for (ll i = 0; i < n; i++) {
        ll c = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin();
        A[c] += a[i]; B[c] += b[i]; // 독초 없음 -> 항상 양의 기여
    }
    vector<ll> pa(M + 1, 0), pb(M + 1, 0);
    for (ll i = 0; i < M; i++) { pa[i + 1] = pa[i] + A[i]; pb[i + 1] = pb[i] + B[i]; }
    while (q--) {
        ll l, r, t; cin >> l >> r >> t;
        ll lo = lower_bound(xs.begin(), xs.end(), l) - xs.begin();
        ll hi = upper_bound(xs.begin(), xs.end(), r) - xs.begin(); // exclusive
        ll sumA = pa[hi] - pa[lo];
        ll sumB = pb[hi] - pb[lo];
        cout << sumA + sumB * t << endl; // 모두 >= 0 이므로 이것이 최적(>=0)
    }
    return 0;
}

5. [서브태스크 4]: \(1 \le N, Q \le 1{,}000\)

\(N\)과 \(Q\)가 모두 작으므로, 매 쿼리마다 가중치를 다시 계산하고 카데인을 돌리는 \(O(NQ)\) 풀이가 통과합니다.

  • 풀이: 위치를 미리 좌표 압축해 둡니다. 각 쿼리에서 주어진 \(t\)로 구간 \([l, r]\) 내 위치들의 가중치를 계산하여 압축된 인덱스 순서의 배열로 만든 뒤, 빈 구간을 허용하는 카데인 알고리즘으로 최대 연속 부분합을 구합니다. 같은 위치의 풀들은 같은 압축 인덱스로 모이므로 자동으로 묶여서 더해집니다.

  • 시간 복잡도: 쿼리당 \(O(N)\), 전체 \(O(NQ) \le 10^6\) 수준으로 매우 여유롭게 통과합니다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
int main() {
    fastio
    ll n, q; cin >> n >> q;
    vector<ll> x(n), a(n), b(n), p(n);
    for (ll i = 0; i < n; i++) cin >> x[i] >> a[i] >> b[i] >> p[i];
    vector<ll> xs(x.begin(), x.end());
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    ll M = xs.size();
    vector<ll> cid(n);
    for (ll i = 0; i < n; i++) cid[i] = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin();
    while (q--) {
        ll l, r, t; cin >> l >> r >> t;
        ll lo = lower_bound(xs.begin(), xs.end(), l) - xs.begin();
        ll hi = upper_bound(xs.begin(), xs.end(), r) - xs.begin() - 1; // inclusive
        if (lo > hi) { cout << 0 << endl; continue; }
        vector<ll> w(hi - lo + 1, 0);
        for (ll i = 0; i < n; i++) if (cid[i] >= lo && cid[i] <= hi) {
            ll val = a[i] + b[i] * t;
            if (p[i]) val = -val;
            w[cid[i] - lo] += val;
        }
        ll best = 0, cur = 0;
        for (ll c = 0; c < (ll)w.size(); c++) {
            cur += w[c];
            if (cur < 0) cur = 0;
            best = max(best, cur);
        }
        cout << best << endl;
    }
    return 0;
}

6. [서브태스크 5]: 모든 \(i\)에 대해 \(b_i = 0\)

모든 \(b_i\)가 \(0\)이면 위치 가중치 \(w(pos) = A_{pos}\)가 시간 \(t\)와 무관한 상수가 됩니다. 따라서 가중치가 고정된 정적인 최대 연속 부분합 구간 쿼리 문제가 됩니다.

  • 풀이: 이 문제는 잘 알려진 "최대 연속 부분합 세그먼트 트리"로 해결됩니다. 압축된 각 위치를 리프로 두고, 각 노드에서 다음 네 값을 관리합니다.
  • tot: 구간 전체 합
  • pre: 왼쪽 끝에서 시작하는 최대 합 (빈 접두사 허용 \(\Rightarrow\) 항상 \(\ge 0\))
  • suf: 오른쪽 끝에서 끝나는 최대 합 (빈 접미사 허용 \(\Rightarrow\) 항상 \(\ge 0\))
  • best: 구간 내 최대 연속 부분합 (빈 구간 허용 \(\Rightarrow\) 항상 \(\ge 0\))

두 자식 \(L\), \(R\)을 합칠 때는
$$ \text{tot} = L.\text{tot} + R.\text{tot}, \quad \text{pre} = \max(L.\text{pre},\, L.\text{tot} + R.\text{pre}) $$
$$ \text{suf} = \max(R.\text{suf},\, R.\text{tot} + L.\text{suf}), \quad \text{best} = \max(L.\text{best},\, R.\text{best},\, L.\text{suf} + R.\text{pre}) $$
로 병합합니다. 쿼리 구간에 걸치는 \(O(\log N)\)개의 노드를 왼쪽에서 오른쪽 순서대로 같은 병합식으로 합치면 답을 얻습니다(순서를 지켜야 suf + pre 항이 올바릅니다).

  • 시간 복잡도: 빌드 \(O(N)\), 쿼리당 \(O(\log N)\), 전체 \(O(N + Q\log N)\)입니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
struct Node { ll tot, pre, suf, best; };
Node mergeN(const Node& L, const Node& R) {
    Node n;
    n.tot  = L.tot + R.tot;
    n.pre  = max(L.pre, L.tot + R.pre);
    n.suf  = max(R.suf, R.tot + L.suf);
    n.best = max(max(L.best, R.best), L.suf + R.pre);
    return n;
}
Node leafN(ll w) { ll z = max(0LL, w); return {w, z, z, z}; }
const Node IDENT = {0, 0, 0, 0}; // 빈 구간
ll M;
vector<Node> tr;
void build(ll node, ll l, ll r, const vector<ll>& w) {
    if (l == r) { tr[node] = leafN(w[l]); return; }
    ll mid = (l + r) / 2;
    build(2 * node, l, mid, w);
    build(2 * node + 1, mid + 1, r, w);
    tr[node] = mergeN(tr[2 * node], tr[2 * node + 1]);
}
bool empt; Node agg;
void query(ll node, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        if (empt) { agg = tr[node]; empt = false; }
        else agg = mergeN(agg, tr[node]);
        return;
    }
    ll mid = (l + r) / 2;
    query(2 * node, l, mid, ql, qr);
    query(2 * node + 1, mid + 1, r, ql, qr);
}
int main() {
    fastio
    ll n, q; cin >> n >> q;
    vector<ll> x(n), a(n), b(n), p(n);
    for (ll i = 0; i < n; i++) cin >> x[i] >> a[i] >> b[i] >> p[i];
    vector<ll> xs(x.begin(), x.end());
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    M = xs.size();
    vector<ll> w(M, 0);
    for (ll i = 0; i < n; i++) {
        ll c = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin();
        ll val = a[i]; if (p[i]) val = -val; // b == 0
        w[c] += val;
    }
    tr.assign(4 * M + 4, IDENT);
    build(1, 0, M - 1, w);
    while (q--) {
        ll l, r, t; cin >> l >> r >> t;
        ll lo = lower_bound(xs.begin(), xs.end(), l) - xs.begin();
        ll hi = upper_bound(xs.begin(), xs.end(), r) - xs.begin() - 1;
        if (lo > hi) { cout << 0 << endl; continue; }
        empt = true;
        query(1, 0, M - 1, lo, hi);
        cout << max(0LL, agg.best) << endl;
    }
    return 0;
}

7. 정해

서브태스크 5의 최대 연속 부분합 세그먼트 트리를 그대로 확장하는 것이 핵심 아이디어입니다. 다만 이제는 각 위치 가중치가 \(t\)의 1차 함수 \(A_{pos} + B_{pos}\cdot t\)이므로, 노드가 들고 있는 네 값 tot, pre, suf, best 역시 \(t\)에 대한 함수가 됩니다.

병합식을 다시 보면, pre는 두 직선의 \(\max\), best는 세 직선의 \(\max\) 형태입니다. 직선들의 \(\max\)는 \(t\)에 대해 위로 볼록한(아래로는 꺾이지 않는) 조각별 선형(piecewise-linear) 함수입니다. 즉 노드의 각 값은 \(t\)에 따라 어떤 직선이 최적인지가 바뀌는 상부 포락선(upper envelope) 입니다. 이를 직접 함수로 들고 다니면 조각 수가 폭발할 수 있습니다.

정해 풀이: 오프라인 + 키네틱 세그먼트 트리 (Kinetic Segment Tree)

  • 풀이: 모든 쿼리를 \(t\) 기준 오름차순으로 정렬한 뒤, 시간 \(t\)를 한 방향으로만 흘려보내며(sweep) 처리합니다. 핵심 관찰은 다음과 같습니다.

병합식 \(\text{best} = \max(L.\text{best}, R.\text{best}, L.\text{suf} + R.\text{pre})\) 등은 모든 고정된 \(t\)에 대해 점별(pointwise)로 성립합니다. 따라서 각 노드가 "현재 시각 \(t\)에서 최적인 직선 하나"만 들고 있어도, 그 직선들로 병합식을 그대로 적용하면 현재 \(t\)에서의 정답을 얻습니다.

그래서 각 노드는 네 값을 각각 직선 하나(m * t + c)로만 저장합니다. 그러나 시간이 흐르면서 어떤 \(\max\) 안에서 다른 후보 직선이 더 커지는 순간(이를 녹는 시각(melt time)이라 합시다)이 생기면, 그 노드의 저장된 직선이 더 이상 최적이 아니게 됩니다. 이때만 그 노드(와 영향을 받는 조상)를 다시 계산(re-heat)하면 됩니다.

구현은 다음과 같습니다.
1. 위치를 좌표 압축하고, 각 리프에 위치 가중치 직선 \(B_{pos}\cdot t + A_{pos}\)를 둡니다. 리프의 pre/suf/best는 \(\max(\text{직선}, 0)\) (빈 구간 허용)입니다.
2. pickMax(a, b, t): 시각 \(t\)에서 두 직선 중 큰 것을 고르고, 동시에 \(t\) 이후에 진 직선이 이긴 직선을 추월하는 다음 교차 시각을 정수 단위로 계산합니다(없으면 \(\infty\)). 두 직선의 교차 시각은 기울기 차이로부터 구하며, 부동소수점 임계값 계산 후 정수 보정으로 정확성을 확보합니다.
3. 각 노드에 그 노드의 병합에서 발생하는 모든 pickMax의 다음 교차 시각의 최솟값 meltT를 저장하고, 서브트리 전체의 최솟값도 함께 관리합니다.
4. 쿼리의 \(t\)로 시각을 전진시킬 때, meltT[node] <= t인 노드만 재귀적으로 방문해 다시 계산합니다(meltT[node] > t인 서브트리는 통째로 건너뜁니다). 이렇게 하면 실제로 "녹은" 노드만 갱신됩니다.
5. 구간 쿼리는 서브태스크 5와 동일하게 \(O(\log N)\)개의 노드를 좌→우 순서로 병합한 뒤 best를 현재 \(t\)에서 평가하고, 음수면 \(0\)으로 보정합니다.

각 노드 값의 상부 포락선은 위로 볼록하므로 한 노드에서 "녹는" 사건의 수는 후보 직선 개수에 비례해 한정되며, 트리 전체에 걸친 재계산 횟수는 \(O(N\log^2 N)\) 수준으로 분할상환(amortized)됩니다. 시각을 단조 증가하게만 전진시키므로(쿼리 정렬) 이미 지나간 교차는 다시 발생하지 않아 효율적입니다.

값의 범위가 크므로(직선의 상수항이 \(5\times10^{17}\) 규모) 모든 누적은 long long으로 처리하고, 교차 시각 계산의 임계값만 long double로 구한 뒤 정수 인접값에서 실제 추월 여부를 검증해 경계 오차를 제거합니다.

  • 시간 복잡도: 좌표 압축 및 정렬 \(O((N + Q)\log)\), 키네틱 세그먼트 트리의 전체 재계산이 \(O(N\log^2 N)\) 분할상환, 쿼리 결합이 \(O(Q\log N)\)입니다. 따라서 전체는 약 \(O((N + Q)\log^2 N)\)이며, \(N, Q \le 2.5\times10^5\)에서 제한 시간 \(2\)초 안에 통과합니다(무작위·적대적 최악 입력 모두 약 \(1\)초 이내 측정).

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

// 한 직선: value = m*t + c
struct Func { ll m, c; };
static inline ll evalF(const Func& f, ll t) { return f.m * t + f.c; }
struct NodeFuncs { Func tot, pre, suf, best; };

ll M;
vector<NodeFuncs> tr;
vector<ll> meltT;     // 노드별 다음 녹는 시각(서브트리 최솟값 포함)
vector<Func> leafLine; // 각 위치의 가중치 직선 (tot)

// 시각 t에서 max(a,b)인 직线을 고르고, 진 직선이 t 이후 처음으로 추월하는 정수 시각을 반환
struct Pick { Func f; ll nxt; };
Pick pickMax(const Func& a, const Func& b, ll t) {
    ll va = evalF(a, t), vb = evalF(b, t);
    const Func *hi, *lo;
    if (va > vb || (va == vb && a.m >= b.m)) { hi = &a; lo = &b; }
    else { hi = &b; lo = &a; }
    ll dm = lo->m - hi->m; // 진 직선이 더 가파를 때만 추월 가능
    ll nxt = INF;
    if (dm > 0) {
        long double thr = (long double)(hi->c - lo->c) / (long double)dm;
        ll cand = (ll)floor(thr) + 1;
        if (cand <= t) cand = t + 1; // 반드시 현재 시각 이후
        if (evalF(*lo, cand) > evalF(*hi, cand)) nxt = cand;
        else { // 부동소수점 경계 보정
            for (ll z = max(cand - 2, t + 1); z <= cand + 2; z++)
                if (z > t && evalF(*lo, z) > evalF(*hi, z)) { nxt = z; break; }
        }
    }
    return { *hi, nxt };
}
// 두 자식을 시각 t에서 병합, 이 노드 자체의 다음 녹는 시각 반환
ll mergeNode(NodeFuncs& nd, const NodeFuncs& L, const NodeFuncs& R, ll t) {
    ll mt = INF;
    nd.tot = { L.tot.m + R.tot.m, L.tot.c + R.tot.c };
    {   Func c2 = { L.tot.m + R.pre.m, L.tot.c + R.pre.c };
        Pick pk = pickMax(L.pre, c2, t); nd.pre = pk.f; mt = min(mt, pk.nxt); }
    {   Func c2 = { R.tot.m + L.suf.m, R.tot.c + L.suf.c };
        Pick pk = pickMax(R.suf, c2, t); nd.suf = pk.f; mt = min(mt, pk.nxt); }
    {   Func cross = { L.suf.m + R.pre.m, L.suf.c + R.pre.c };
        Pick p1 = pickMax(L.best, R.best, t);
        Pick p2 = pickMax(p1.f, cross, t);
        nd.best = p2.f; mt = min(mt, min(p1.nxt, p2.nxt)); }
    return mt;
}
void build(ll node, ll l, ll r, ll t) {
    if (l == r) {
        Func ln = leafLine[l], zero = {0, 0};
        tr[node].tot = ln;
        Pick pk = pickMax(ln, zero, t); // 빈 구간 허용 -> max(line, 0)
        tr[node].pre = tr[node].suf = tr[node].best = pk.f;
        meltT[node] = pk.nxt; return;
    }
    ll mid = (l + r) / 2;
    build(2 * node, l, mid, t); build(2 * node + 1, mid + 1, r, t);
    ll mt = mergeNode(tr[node], tr[2 * node], tr[2 * node + 1], t);
    meltT[node] = min(mt, min(meltT[2 * node], meltT[2 * node + 1]));
}
// 시각 t로 전진: meltT <= t 인 노드만 재계산
void heaten(ll node, ll l, ll r, ll t) {
    if (meltT[node] > t) return;
    if (l == r) {
        Func ln = leafLine[l], zero = {0, 0};
        Pick pk = pickMax(ln, zero, t);
        tr[node].tot = ln;
        tr[node].pre = tr[node].suf = tr[node].best = pk.f;
        meltT[node] = pk.nxt; return;
    }
    ll mid = (l + r) / 2;
    heaten(2 * node, l, mid, t); heaten(2 * node + 1, mid + 1, r, t);
    ll mt = mergeNode(tr[node], tr[2 * node], tr[2 * node + 1], t);
    meltT[node] = min(mt, min(meltT[2 * node], meltT[2 * node + 1]));
}
bool empt; NodeFuncs agg;
void query(ll node, ll l, ll r, ll ql, ll qr, ll t) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        if (empt) { agg = tr[node]; empt = false; }
        else { NodeFuncs res; mergeNode(res, agg, tr[node], t); agg = res; }
        return;
    }
    ll mid = (l + r) / 2;
    query(2 * node, l, mid, ql, qr, t);
    query(2 * node + 1, mid + 1, r, ql, qr, t);
}
int main() {
    fastio
    ll n, q; cin >> n >> q;
    vector<ll> X(n), A(n), B(n), P(n);
    for (ll i = 0; i < n; i++) cin >> X[i] >> A[i] >> B[i] >> P[i];
    vector<ll> xs(X.begin(), X.end());
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    M = xs.size();
    vector<ll> Apos(M, 0), Bpos(M, 0);
    for (ll i = 0; i < n; i++) {
        ll c = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
        ll s = P[i] ? -1 : 1;
        Apos[c] += s * A[i]; Bpos[c] += s * B[i];
    }
    tr.assign(4 * M + 4, NodeFuncs{});
    meltT.assign(4 * M + 4, INF);
    leafLine.assign(M, Func{0, 0});
    for (ll i = 0; i < M; i++) leafLine[i] = { Bpos[i], Apos[i] };

    struct Qr { ll l, r, t, idx; };
    vector<Qr> qs(q);
    for (ll i = 0; i < q; i++) { cin >> qs[i].l >> qs[i].r >> qs[i].t; qs[i].idx = i; }
    sort(qs.begin(), qs.end(), [](const Qr& a, const Qr& b) { return a.t < b.t; });
    vector<ll> ans(q);
    build(1, 0, M - 1, 0);
    ll curT = 0;
    for (auto& Q : qs) {
        if (Q.t > curT) { heaten(1, 0, M - 1, Q.t); curT = Q.t; }
        ll lo = lower_bound(xs.begin(), xs.end(), Q.l) - xs.begin();
        ll hi = upper_bound(xs.begin(), xs.end(), Q.r) - xs.begin() - 1;
        if (lo > hi) { ans[Q.idx] = 0; continue; }
        empt = true;
        query(1, 0, M - 1, lo, hi, Q.t);
        ll best = evalF(agg.best, Q.t);
        if (best < 0) best = 0;
        ans[Q.idx] = best;
    }
    for (ll i = 0; i < q; i++) cout << ans[i] << endl;
    return 0;
}

이 정해는 위치 충돌·독초·시간에 따른 부호 변화가 모두 섞인 무작위 입력 약 \(5{,}000\)개와, 모든 녹는 사건이 발생하도록 설계한 적대적 입력에서 \(O(N)\) 카데인 브루트포스와 완전히 동일한 답을 출력함을 확인했습니다.

평가 및 의견

알파카컵 1회: I - 알파카의 식사

개요
출제자 난이도 Diamond I 다이아몬드 I 의견 1 / 50 공개 집계 (커뮤니티 난이도, 주요 주제, 품질)는 의견이 충분히 모이면 공개됩니다.
티어 투표 분포
Diamond I 다이아몬드 I 1

Log in to rate problems.

개별 의견

풀이 제출

알파카컵 1회: I - 알파카의 식사

게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다. 로그인하고 제출하기
작성 중 Rush? 언어 레퍼런스 읽기 ↗
공개
C++20 Tab 들여쓰기 · Ctrl+/ 주석 토글 · Enter 자동 들여쓰기
행1 열1 1줄 0자 공백: 4 · UTF-8