RT,完成了一道交互题的代码,在网上提交AC,请问怎么在本地测试样例 老师让做
题目:https://uoj.ac/problem/660 Code:
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define lc o << 1
#define rc o << 1 | 1
#define i64 long long
const int MN = 2e5 + 5;
const i64 INF = 1e17;
int n, q;
i64 sum[MN << 2], maxx[MN << 2], minn[MN << 2], tag[MN << 2];
i64 max(i64 x, i64 y) {return x > y ? x : y;}
i64 min(i64 x, i64 y) {return x < y ? x : y;}
void push_up(int o) {
sum[o] = sum[lc] + sum[rc];
maxx[o] = max(maxx[lc], maxx[rc]);
minn[o] = min(minn[lc], minn[rc]);
}
void push_down(int o, int len) {
if (!tag[o]) return ;
tag[lc] += tag[o], tag[rc] += tag[o];
sum[lc] += tag[o] * (i64)((len + 1) / 2), sum[rc] += tag[o] * (i64)(len / 2);
maxx[lc] += tag[o], maxx[rc] += tag[o];
minn[lc] += tag[o], minn[rc] += tag[o];
tag[o] = 0;
}
void update(int o, int l, int r, int ql, int qr, int k) {
if (qr < l || ql > r) return ;
if (ql <= l && r <= qr) {
tag[o] += k;
sum[o] += k * (r - l + 1);
maxx[o] += k, minn[o] += k;
return ;
}
push_down(o, r - l + 1);
int mid = l + (r - l >> 1);
update(lc, l, mid, ql, qr, k), update(rc, mid + 1, r, ql, qr, k);
push_up(o);
}
i64 query(int o, int l, int r, int x) {
if (l == r) return sum[o];
push_down(o, r - l + 1);
int mid = l + (r - l >> 1);
if (x <= mid) return query(lc, l, mid, x);
else return query(rc, mid + 1, r, x);
}
i64 binary_solve(i64 x) {
int o = 1, l = 0, r = q;
i64 ma = -INF, mn = INF, last = query(1, 0, q, q);
while (l < r) {
push_down(o, r - l + 1);
int mid = l + (r - l >> 1);
if (max(maxx[rc], ma) - min(minn[rc], mn) > x) {
o = rc;
l = mid + 1;
}
else {
ma = max(maxx[rc], ma), mn = min(minn[rc], mn);
r = mid;
o = lc;
}
}
if (minn[o] < mn) return x - (ma - last); //碰下壁 :last < 0
// ma - last为x-q负值减掉的量,即最后一段x <= i <= q区间v[i]<0的累加和的相反数
else return last - mn; //碰上壁 last > c[i]
// last - mn为正值加上的量,可以根据碰下壁结论退出
}
vector<int> place[MN], add[MN], ans;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size(), q = l.size();
for (int i = 0; i < q; ++i) {
place[l[i]].emplace_back(i);
add[l[i]].emplace_back(v[i]);
place[r[i] + 1].emplace_back(i);
add[r[i] + 1].emplace_back(-v[i]);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < add[i].size(); ++j)
update(1, 0, q, place[i][j] + 1, q, add[i][j]); //区间加
if (maxx[1] - minn[1] <= c[i]) //如果极差不大于等于容量,不碰壁
ans.emplace_back(query(1, 0, q, q) - minn[1]); //则肯定没有超过容量,直接累加
else
ans.emplace_back(binary_solve(c[i])); //否则二分寻找那个x
}
return ans;
}
悬赏关注,在线等很急