QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130303#3300. Cactus Competitionsinsop90WA 4ms20064kbC++143.6kb2023-07-23 20:10:382023-07-23 20:10:41

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 20:10:41]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:20064kb
  • [2023-07-23 20:10:38]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 5;
int n, m, a[maxn], b[maxn], f[maxn][25][2], g[maxn][25], ans, tot;
struct ASK {
	int x, xx, y, yy;
}Q[maxn << 2];
struct SMT {
	int sum, tag;
}tr[maxn << 2];
struct Rask {
	int l, r, op;
};
vector<Rask> vec[maxn];
int querymax(int l, int r, int op) {
	int len = log2(r - l + 1);
//	cout << l << " " << r << " " << len << " " << f[l][len][op] << endl;
	return max(f[l][len][op], f[r - (1 << len) + 1][len][op]);
}
int querymin(int l, int r, int op) {
	int len = log2(r - l + 1);
	return min(g[l][len], g[r - (1 << len) + 1][len]);
}
int ls(int p) {
	return p << 1;
}
int rs(int p) {
	return p << 1 | 1;
}
void pushup(int p) {
	if(tr[p].tag) return;
	tr[p].sum = tr[ls(p)].sum + tr[rs(p)].sum;
}
void update(int p, int l, int r, int nl, int nr, int op) {
	if(nl <= l && r <= nr) {
		tr[p].tag += op;
		if(!tr[p].tag) tr[p].sum = tr[ls(p)].sum + tr[rs(p)].sum;
		else if(tr[p].tag == 1) tr[p].sum = r - l + 1;
		return;
	}
	int mid = (l + r) >> 1;
	if(nl <= mid) update(ls(p), l, mid, nl, nr, op);
	if(nr > mid) update(rs(p), mid + 1, r, nl, nr, op);
	pushup(p);
}
signed main() {
	scanf("%lld%lld", &n, &m);
	for(int i = 1;i <= n;i++) scanf("%lld", &a[i]), f[i][0][0] = a[i];
	for(int i = 1;i <= m;i++) scanf("%lld", &b[i]), f[i][0][1] = b[i];
	for(int i = 1;(1 << i) <= n;i++) for(int j = 1;j + (1 << i) - 1 <= n;j++) f[j][i][0] = max(f[j][i - 1][0], f[j + (1 << i - 1)][i - 1][0]);
//	cout << f[1][0][1] << endl;
	for(int i = 1;(1 << i) <= m;i++) for(int j = 1;j + (1 << i) - 1 <= m;j++) f[j][i][1] = max(f[j][i - 1][1], f[j + (1 << i - 1)][i - 1][1]), g[j][i] = min(g[j][i - 1], g[j + (1 << i - 1)][i - 1]);
	for(int i = 1;i <= n;i++) {
		int l = 1, r = m, res = 0;
		while(l <= r) {
			int mid = (l + r) >> 1; 
			if(querymax(1, mid, 'b' - 'a') + a[i] < 0) res = mid, l = mid + 1;
			else r = mid - 1;  
		}
		if(!res) continue;
//		cout << res << " " << querymax(1, res, 'b' - 'a') << " " << f[1][0][1] << endl;
		int p = querymin(1, res, 'b' - 'a');
		l = 1, r = i, res = i;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(querymax(mid, i, 'a' - 'a') + p < 0) res = mid, r = mid - 1;
			else l = mid + 1;
		}
		Q[++ tot] = {res, i, 1, n};
//		cout << "1: " << res << " " << i << endl;
	}
	for(int i = 1;i <= n;i++) {
		int l = 1, r = m, res = m + 1;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(querymax(mid, m, 'b' - 'a') + a[i] < 0) res = mid, r = mid - 1;
			else l = mid + 1;
		}
		if(res == m + 1) continue;
		int p = querymin(res, m, 'b' - 'a');
		l = i, r = m, res = i;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(querymax(i, mid, 'a' - 'a') + p < 0) res = mid, l = mid + 1;
			else r = mid - 1;
		}
		Q[++ tot] = {1, n, i, res};
//		cout << "2: " << i << " " << res << endl;
	}
	for(int i = 1;i <= n;i++) {
		if(a[i] + querymax(1, m, 'b' - 'a') < 0) Q[++ tot] = {1, i, i, n};
	}
	int rt = 0;
	for(int i = 1;i <= m;i++) if(b[i] < b[rt]) rt = i;
	for(int i = 1;i <= n;i++) { 
		int now = i - 1;
		while(now < n && a[now + 1] + b[rt] < 0) now ++;
		if(now == i - 1) continue;
		Q[++ tot] = {i, now, i, now};
		i = now;
	}
	for(int i = 2;i <= n;i++) Q[++ tot] = {i, i, 1, i - 1};
	for(int i = 1;i <= tot;i++) {
//		cout << Q[i].x << " " << Q[i].y << " " << Q[i].xx << " " << Q[i].yy << endl;
		vec[Q[i].x].push_back({Q[i].y, Q[i].yy, 1}), vec[Q[i].xx + 1].push_back({Q[i].y, Q[i].yy, -1});
	}
	for(int i = 1;i <= n + 1;i++) {
//		cout << tr[1].sum << endl;
		ans += tr[1].sum;
		for(Rask t : vec[i]) update(1, 1, n, t.l, t.r, t.op);
	}
	printf("%lld\n", n * n - ans);
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 19408kb

input:

3 3
-1 0 1
-1 0 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 20064kb

input:

3 3
-1 0 1
1 0 1

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 1ms
memory: 19736kb

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: 4ms
memory: 19568kb

input:

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

output:

19

result:

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