我的树状数组连样例都过不了
查看原帖
我的树状数组连样例都过不了
162196
伟大的王夫子楼主2020/6/14 10:51

求助

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;char buf[100010], *p1, *p2;
//#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++
template<class item>
inline item read() {
    item res = 0;
    bool negative = 0;
    char ch = getchar();
    while (!isdigit(ch)) negative |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return negative ? -res : res;
}
template<class item>
inline item read(item & t) {
    t = read<item>();
    return t;
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
    read(t), read(args...);
}
int n, cnt;
long long sum[200010], t;
long long a[400010];
int c[400010];
void add(int x, int y) {
	while (x <= cnt) {
		c[x] += y;
		x += x & -x; 
	}
} 
int ask(int x) {
	int ans = 0;
	while (x) {
		ans += c[x];
		x -= x & -x;
	}
	return ans;
}
int val(int x) {
	return lower_bound(a + 1, a + n + 1, x) - a;
}
long long ans = 0;
int main() {
	cin >> n >> t;
	for (register int i = 1; i <= n; ++i) {
		sum[i] = sum[i - 1] + read<int>(); 
		a[++cnt] = sum[i], a[++cnt] = sum[i] + t;
	}
	sort(a + 1, a + cnt + 1);
	for (register int i = n; i ; --i) {
		int x = val(sum[i] + t), y = val(sum[i]);
		ans += ask(x - 1);
		add(y, 1);
	} 
	cout << ans;
	
} 
2020/6/14 10:51
加载中...