QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130143#3300. Cactus CompetitionAlinxesterWA 3ms11868kbC++142.5kb2023-07-23 17:11:102023-07-23 17:11:12

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-23 17:11:12]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:11868kb
  • [2023-07-23 17:11:10]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define mod 998244353
#define int128 __int128
#define base 23333
#define base2 19260817
#define db double
#define ldb long double
#define eps 1e-8
#define cmpeps 1e-18
#define lowbit(x) (x & -x)
#define un unsigned
#define rep(i,x,y) for (int i = (x); i <= (y); ++i)
#define drep(i,x,y) for (int i = (x); i >= (y); --i)
#define go(i,u) for (int i = head[u]; i; i = edge[i].next)
#define go_(i,u) for (int i = head[u]; ~i; i = edge[i].next)
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
//char buf[1<<21],*p1=buf,*p2=buf;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> inline T rnd(T l,T r) {return uniform_int_distribution<T>(l , r)(rng);}
template<typename T> inline void read (T &t) {
	t = 0; char f = 0, ch = getchar(); ldb d = 0.1;
	while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
	while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
	if (ch == '.') {
		ch = getchar();
		while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
	}
	t = (f ? -t : t);
}
template <typename T, typename... Args>
	inline void read (T& t, Args&... args) { read(t); read(args...); }
inline void write (int x) {
	if (x >= 10) write(x / 10);
	cout << (ll) (x % 10);
}
const int N = 2e5 + 2, INF = 1e18 + 2;
int n, m, a[N], b[N], p[N];
int L[N], R[N], lvis[N], rvis[N]; 
int sum[N], ans;
inline bool p_cmp (int x, int y) {
	return a[x] > a[y]; }
signed main() {
	read(n, m);
	rep (i, 1, n) read(a[i]), p[i] = i;
	rep (i, 1, m) read(b[i]);
	sort(p + 1, p + n + 1, p_cmp);
	int l = 1, r = m, lmn, rmn;
	lmn = rmn = INF;
	rep (i, 1, n) {
		for (; l <= m && a[p[i]] + b[l] < 0; ++l) lmn = min(lmn, b[l]);
		for (; r && a[p[i]] + b[r] < 0; --r) rmn = min(rmn, b[r]);
		L[i] = lmn, R[i] = rmn;
	}
	drep (i, n, 1) {
		for (int j = p[i]; j && !lvis[j] && L[i] + a[j] < 0; --j) lvis[j] = 1;
		for (int j = p[i]; j <= n && !rvis[j] && R[i] + a[j] < 0; --j) rvis[i] = 1;
	}
	int mx = -INF, mn = INF;
	rep (i, 1, m) mn = min(mn, b[i]), mx = max(mx, b[i]);
	rep (i, 1, n) sum[i] = sum[i - 1] + (!rvis[i]);
	l = r = n + 1;
	drep (i, n, 1) {
		if (mn + a[i] >= 0) l = i;
		if (mx + a[i] < 0) r = i;
		if (!lvis[i] && l < r) ans += sum[r - 1] - sum[l - 1];
	}
	printf("%lld\n", ans);
return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 11848kb

input:

3 3
-1 0 1
-1 0 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 11860kb

input:

3 3
-1 0 1
1 0 1

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 3ms
memory: 11852kb

input:

10 10
145195799 312862766 143966779 -11056226 -503624929 636383890 -182650312 -382759112 -290767690 377894950
-845235881 -418232930 -600566938 -957917357 -181139226 125255273 -175406945 740226783 -750456842 325848662

output:

0

result:

ok single line: '0'

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 11868kb

input:

10 10
923415743 -503391272 885740174 329644337 -693052351 -53764994 731859967 -834732760 -57751504 151969590
553689579 313784278 -12090771 921222379 -378313551 819586787 -373658045 559813071 671861309 268258615

output:

20

result:

wrong answer 1st lines differ - expected: '13', found: '20'