关于本地测试交互题
  • 板块学术版
  • 楼主memset_0x3f
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/4/4 18:23
  • 上次更新2023/10/28 04:37:17
查看原帖
关于本地测试交互题
333478
memset_0x3f楼主2022/4/4 18:23

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;
}

悬赏关注,在线等很急

2022/4/4 18:23
加载中...