UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214526#574. t3Running_a_way039ms2480kbC++112.9kb2024-11-19 20:30:242024-11-19 23:02:02

answer

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 100010;
int n; ll X, Y, Z;
int a[N], b[N];
namespace subtask2 {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    void main() {
//        printf("In sub2:\n");
        for (int i = 1; i <= n; i++) 
            if(a[i] > b[i]) q.push({i, a[i] - b[i]});
        ll eps1 = 0, eps2 = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            if(a[i] >= b[i]) continue;
            ll delta = b[i] - a[i];
            while(q.size() && q.top().second <= delta) {
                delta -= q.top().second;
                ans += 1ll * abs(i - q.top().first) * q.top().second;
                q.pop();
            }
            if(delta && q.size()) {
                pii pr = q.top(); q.pop();
                ans += 1ll * abs(i - pr.first) * delta;
                q.push({pr.first, pr.second - delta});
                delta = 0;
            }
            if(delta) eps1 += delta;
        }
        while(q.size()) eps2 += q.top().second, q.pop();
        if(eps1) ans += X * eps1;
        if(eps2) ans += Y * eps2;
        printf("%lld\n", ans);
    }
}

namespace subtaskall {
    priority_queue<pii> q1, q2; // q1 存溢出,q2 存缺少,第一维放坐标,第二维放 size
    void main() {
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            if(a[i] < b[i]) {
                int delta = b[i] - a[i];
                while(q1.size() && delta) {
                    int j = q1.top().first, D = q1.top().second, d1 = min(q1.top().second, delta);
                    if((i - j) * Z > X + Y) ans += d1 * (X + Y);
                    else ans += d1 * (i - j) * Z;
                    delta -= d1;
                    q1.pop();
                    if(D > d1) q1.push({j, D - d1});
                }
                if(delta) q2.push({i, delta});
            } else if(a[i] > b[i]) {
                int delta = a[i] - b[i];
                while(q2.size() && delta) {
                    int j = q2.top().first, D = q2.top().second, d1 = min(q2.top().second, delta);
                    if((i - j) * Z > X + Y) ans += d1 * (X + Y);
                    else ans += d1 * (i - j) * Z;
                    delta -= d1;
                    q2.pop();
                    if(D > d1) q2.push({j, D - d1});
                }
                if(delta) q1.push({i, delta});
            }
        }
        while(q2.size()) ans += X * q2.top().second, q2.pop();
        while(q1.size()) ans += Y * q1.top().second, q1.pop();
        printf("%lld\n", ans);
    }
}

int main() {
//    freopen("A1.in", "r", stdin);
//    freopen("A.out", "w", stdout);
    scanf("%d%lld%lld%lld", &n, &X, &Y, &Z);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
    if(X == Y && X == 1e8 && Z == 1) subtask2::main();
    else subtaskall::main();
    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1248kb

input:

50 4 401 83
1 9
0 10
1 1
7 5
6 2
6 10
5 10
5 5
4 4
10 8
8 3
4 8
8 0
1 2
8 9
9 9
4 6
8 7
3 10
2 4
9 3...

output:

15566

result:

wrong answer 1st words differ - expected: '12399', found: '15566'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 21ms
memory: 2480kb

input:

100000 100000000 100000000 1
4 1
7 1
7 6
7 5
7 5
6 6
5 1
1 4
2 0
3 0
5 7
1 9
1 1
6 8
2 5
7 7
7 9
6 3...

output:

211756751567

result:

wrong answer 1st words differ - expected: '211716275189', found: '211756751567'

Subtask #3:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 18ms
memory: 2024kb

input:

100000 30694440 93757838 144
1 4
0 5
9 3
3 8
6 9
7 4
3 5
6 1
6 6
4 5
10 0
9 4
7 4
9 1
5 4
8 4
2 0
10...

output:

12891090912

result:

wrong answer 1st words differ - expected: '11782941072', found: '12891090912'