QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302378#7615. Sequence Foldingdefyers#WA 0ms7692kbC++202.4kb2024-01-10 20:09:412024-01-10 20:09:42

Judging History

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

  • [2024-01-10 20:09:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7692kb
  • [2024-01-10 20:09:41]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define int long long
using ll = long long;
using LL = long long;
using pii = pair<int, int>;

const int N = 5e5 + 11;
const int INF = 1LL << 60;
int a[N];

int n, q; 
struct SegTree{
	int t[N << 2], ans = 0;
	void build(int v, int l, int r){
		if(l == r){
			t[v] = a[v]; ans += t[v];
		}else{
			int m = (l + r) / 2;
			build(v * 2 + 1, l, m);
			build(v * 2 + 2, m + 1, r);
			int P = 0, Q = 0;
			int mx = 0;
			for(int i = m; i >= l; i--){
				mx = max(mx, a[i]);
				P += mx;
			}

			mx = 0;
			for(int i = m + 1; i <= r; i++){
				mx = max(mx, a[i]);
				Q += mx;
			}
			ans += P * Q;
			t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
		}
	}
	void _add(int qi, int qv, int v, int l, int r){
		if(l == r) t[v] += qv;
		else {
			int m = (l + r) / 2;
			if(qi <= m) _add(qi, qv, v * 2 + 1, l, m);
			else _add(qi, qv, v * 2 + 2, m + 1, r);
			t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
		}
	}
	int larger_first(int ql, int qr, int qv, int v, int l, int r){
		if(qr < ql || qr < l || r < ql || t[v] <= qv) return INF;
		if(l == r) return l;
		else {
			int m = (l + r) / 2;
			int a = larger_first(ql, qr, qv, v * 2 + 1, l, m);
			if(a != INF) return a;
			int b = larger_first(ql, qr, qv, v * 2 + 2, m + 1, r);
			return b;
		}
	}
	int larger_last(int ql, int qr, int qv, int v, int l, int r){
		if(qr < ql || qr < l || r < ql || t[v] <= qv) return INF;
		if(l == r) return l;
		else {
			int m = (l + r) / 2;
			int a = larger_last(ql, qr, qv, v * 2 + 2, m + 1, r);
			if(a != INF) return a;
			int b = larger_last(ql, qr, qv, v * 2 + 1, l, m);
			return b;
		}
	}
	void add(int x){
		_add(x, 1, 0, 1, n);
		
	}
	void sub(int x){
		_add(x, -1, 0, 1, n);
	}
} ST_MAX, ST_MIN;

void add(int x){
	ST_MAX.add(x);
	ST_MIN.sub(x);
}

void sub(int x){
	ST_MAX.sub(x);
	ST_MIN.add(x);
}

void solve(int TC) {
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	ST_MAX.build(0, 1, n);
	for(int i = 1; i <= n; i++) a[i] = -a[i];
	ST_MIN.build(0, 1, n);
	for(int i = 0; i < q; i++){
		char op; cin >> op;
		int x; cin >> x;
		if(op == '+') add(x);
		else sub(x);
		cout << ST_MAX.ans + ST_MIN.ans << '\n';
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7692kb

input:

8 3
1 5 8

output:

40
80
120
160
200
240
280
320

result:

wrong answer 1st lines differ - expected: '2', found: '40'