社区讨论

求问代码运行速度问题

__RainCappuccino_
学术版参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi5il0xz
此快照首次捕获于
2025/11/19 12:40
3 个月前
此快照最后确认于
2025/11/19 13:12
3 个月前
查看原帖
在以下代码中注释掉第 225225 行，在 n=3×105n = 3 \times 10^5 的数据下从 3.1 秒变为了 0.8 秒，注释掉 224224 行仍然是 3.1 秒，但是理论上这两行都是差分的一部分，复杂度应该是一样的吧
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
typedef long long ll;
typedef pair<int, int> pi;

namespace Fread
{
	const int SIZE = 1 << 16;
	char buf[SIZE], *S, *T;
	inline char getchar() { if (S == T) { T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n'; } return *S++; }
}
using namespace Fread;
namespace Fwrite
{
	const int SIZE = 1 << 16;
	char buf[SIZE], *S = buf, *T = buf + SIZE;
	inline void flush() { fwrite(buf, 1, S - buf, stdout); S = buf; }
	inline void putchar(char c) { *S++ = c; if (S == T) flush(); }
	struct NTR { ~NTR() { flush(); } } ztr;
}
using namespace Fwrite;
#define getchar Fread::getchar
#define putchar Fwrite::putchar
namespace Fastio
{
	struct Reader
	{
		template <typename T> Reader& operator >> (T &x)
		{
			x = 0;
			short f = 1;
			char c = getchar();
			while (c < '0' || c > '9') { if (c == '-') f *= -1; c = getchar(); }
			while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
			x *= f;
			return *this;
		}
		Reader& operator >> (double &x)
		{
			x = 0;
			double t = 0;
			short f = 1, s = 0;
			char c = getchar();
			while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }
			while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();
			if (c == '.') c = getchar();
			else { x *= f; return *this; }
			while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();
			while (s--) t /= 10.0;
			x = (x + t) * f;
			return *this;
		}
		Reader& operator >> (long double &x)
		{
			x = 0;
			long double t = 0;
			short f = 1, s = 0;
			char c = getchar();
			while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }
			while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();
			if (c == '.') c = getchar();
			else { x *= f; return *this; }
			while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();
			while (s--) t /= 10.0;
			x = (x + t) * f;
			return *this;
		}
		Reader& operator >> (__float128 &x)
		{
			x = 0;
			__float128 t = 0;
			short f = 1, s = 0;
			char c = getchar();
			while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }
			while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();
			if (c == '.') c = getchar();
			else { x *= f; return *this; }
			while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();
			while (s--) t /= 10.0;
			x = (x + t) * f;
			return *this;
		}
		Reader& operator >> (char &c)
		{
			c = getchar();
			while (c == ' ' || c == '\n' || c == '\r') c = getchar();
			return *this;
		}
		Reader& operator >> (char *str)
		{
			int len = 0;
			char c = getchar();
			while (c == ' ' || c == '\n' || c == '\r') c = getchar();
			while (c != ' ' && c != '\n' && c != '\r') str[len++] = c, c = getchar();
			str[len] = '\0';
			return *this;
		}
		Reader& operator >> (string &str)
		{
			str.clear();
			char c = getchar();
			while (c == ' ' || c == '\n' || c == '\r') c = getchar();
			while (c != ' ' && c != '\n' && c != '\r') str.push_back(c), c = getchar();
			return *this;
		}
		Reader() {}
	} cin;
	const char endl = '\n';
	struct Writer
	{
		const int Setprecision = 6;
		typedef int mxdouble;
		template <typename T> Writer& operator << (T x)
		{
			if (x == 0) { putchar('0'); return *this; }
			if (x < 0) putchar('-'), x = -x;
			static short sta[40];
			short top = 0;
			while (x > 0) sta[++top] = x % 10, x /= 10;
			while (top > 0) putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer& operator << (double x)
		{
			if (x < 0) putchar('-'), x = -x;
			mxdouble _ = x;
			x -= (double)_;
			static short sta[40];
			short top = 0;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			if (top == 0) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			putchar('.');
			for (int i = 0; i < Setprecision; i++) x *= 10;
			_ = x;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			for (int i = 0; i < Setprecision - top; i++) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer& operator << (long double x)
		{
			if (x < 0) putchar('-'), x = -x;
			mxdouble _ = x;
			x -= (long double)_;
			static short sta[40];
			short top = 0;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			if (top == 0) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			putchar('.');
			for (int i = 0; i < Setprecision; i++) x *= 10;
			_ = x;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			for (int i = 0; i < Setprecision - top; i++) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer& operator << (__float128 x)
		{
			if (x < 0) putchar('-'), x = -x;
			mxdouble _ = x;
			x -= (__float128)_;
			static short sta[40];
			short top = 0;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			if (top == 0) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			putchar('.');
			for (int i = 0; i < Setprecision; i++) x *= 10;
			_ = x;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			for (int i = 0; i < Setprecision - top; i++) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer& operator << (char c) { putchar(c); return *this; }
		Writer& operator << (char *str)
		{
			int cur = 0;
			while (str[cur]) putchar(str[cur++]);
			return *this;
		}
		Writer& operator << (const char *str)
		{
			int cur = 0;
			while (str[cur]) putchar(str[cur++]);
			return *this;
		}
		Writer& operator << (string str)
		{
			int st = 0, ed = str.size();
			while (st < ed) putchar(str[st++]);
			return *this;
		}
		Writer() {}
	} cout;
}
using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
int n, m, V;
int a[N], b[N];
int p[N], q[N];
ll c[N];
int bel[N], bl[N], br[N];
ll s[N], arr[N];
int bsiz;
inline void add (int x, ll d) {
}
inline ll sum (int x) {
	ll res = 0;
	for (int i = 1; i < bel[x]; i ++) res += s[i];
	for (int i = bl[bel[x]]; i <= x; i ++) res += arr[i];
	return res;
}
inline void upd (int x, int v) {
	x --;
	for (int l = 1, r = 1; l <= x; l = r + 1) {
		r = x / (x / l);
		ll val = 1ll * ((x / l) + 1) * v;
		arr[l] += val, s[bel[l]] += val;
		arr[r + 1] -= val, s[bel[r + 1]] -= val;
	}
	arr[x + 1] += v;
	s[bel[x + 1]] += v;
}

int main() {
	freopen("france20.in", "r", stdin);
	freopen("france.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin >> n >> m >> V;
	for (int i = 1; i <= n; i ++) cin >> p[i] >> q[i];
	for (int i = 1; i <= m; i ++) cin >> a[i] >> b[i];
	bsiz = sqrt(V);
	for (int i = 1; i <= V; i ++) {
		bel[i] = (i - 1) / bsiz + 1;
		if (bel[i] != bel[i - 1]) br[bel[i - 1]] = i - 1, bl[bel[i]] = i;
	}
	br[bel[V]] = V;
	int j = 0;
	bool flag = 1;
	for (int i = 1; i <= m; i ++) {
		if (!flag) {
			cout << -1 << endl;
			continue;
		}
		while (sum(a[i]) < b[i]) {
			if (j < n) ++ j, upd (q[j], p[j]);
			else {flag = 0; break;}
		}
		if (!flag) cout << -1 << endl;
		else cout << j << ' ' << endl;
	}
	return 0;
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...