WA on #5 #10 求条
查看原帖
WA on #5 #10 求条
941431
Autream楼主2024/11/25 21:02
// Problem: P5459 [BJOI2016] 回转寿司
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5459
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Date: 2024/11/25 20:42:28
// Author: Li_Feiy

#include <bits/stdc++.h>
#define arrout(a, n) rep(i, 1, n) printk(a[i])
#define arrin(a, n) rep(i, 1, n) a[i] = read()
#define rep(i, x, n) for(int i = x; i <= n; i++)
#define dep(i, x, n) for(int i = x; i >= n; i--)
#define erg(i, x) for(int i = head[x]; i; i = e[i].nex)
#define dbg(x) std::cout << #x << ":" << x << " "
#define mem(a, x) memset(a, x, sizeof a)
#define all(x) x.begin(), x.end()
#define arrall(a, n) a + 1, a + 1 + n
#define PII std::pair<int, int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
int read() {
	char ch = getchar();
	int r = 0, w = 1;
	while(ch < '0' || ch > '9') w = ch == '-' ? -1 : w, ch = getchar();
	while(ch >= '0' && ch <= '9') r = (r << 3) + (r << 1) + (ch ^ 48), ch = getchar();
	return r * w;
}

void print(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}template<typename ...Args>
void print(int t, Args... args) { print(t), print(args...); }

void printl(int x) { print(x), putchar('\n'); }
template<typename ...Args>
void printl(int t, Args... args) { printl(t), printl(args...); }

void printk(int x) { print(x), putchar(' '); }
template<typename ...Args>
void printk(int t, Args ... args) { printk(t), printk(args...); }

CI N = 1e6 + 5;
int n, L, R, ans, len, b[N], s[N];
struct Binaru_Indexed_Tree {
	int c[N];
	int lowbit(int x) { return x & (-x); }
	void update(int x, int v) { for(int i = x; i <= len; i += lowbit(i)) c[i] += v; }
	int query(int l, int r) {
		int ans = 0;
		for(int i = l - 1; i; i -= lowbit(i)) ans -= c[i];
		for(int i = r; i; i -= lowbit(i)) ans += c[i];
		return ans;
	}
} bit;
int getid(int x) { return std::l_b(arrall(b, len), x) - b; }
signed main() {
	n = read(), L = read(), R = read();
	rep(i, 1, n) s[i] = s[i - 1] + read(), b[++ len] = s[i], b[++ len] = s[i] - L, b[++ len] = s[i] - R;
	b[++ len] = 0;
	std::sort(arrall(b, len));
	len = std::unique(arrall(b, len)) - b - 1;
	bit.update(getid(0), 1);
	rep(i, 1, n) bit.update(getid(s[i]), 1), ans += bit.query(getid(s[i] - R), getid(s[i] - L));
	print(ans);
	return 0;
}
2024/11/25 21:02
加载中...