QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#586580	#6837. AC Automaton	cyj888	WA	4ms	33040kb	C++11	8.7kb	2024-09-24 14:15:40	2024-09-24 14:15:40

Judging History

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

[2024-09-24 14:15:40]
评测

测评结果：WA
用时：4ms
内存：33040kb

查看

[2024-09-24 14:15:40]
提交

answer

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#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")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma G++ optimize(1)
#pragma G++ optimize(2)
#pragma G++ optimize(3)
#pragma G++ optimize("Ofast")
#pragma G++ optimize("inline")
#pragma G++ optimize("-fgcse")
#pragma G++ optimize("-fgcse-lm")
#pragma G++ optimize("-fipa-sra")
#pragma G++ optimize("-ftree-pre")
#pragma G++ optimize("-ftree-vrp")
#pragma G++ optimize("-fpeephole2")
#pragma G++ optimize("-ffast-math")
#pragma G++ optimize("-fsched-spec")
#pragma G++ optimize("unroll-loops")
#pragma G++ optimize("-falign-jumps")
#pragma G++ optimize("-falign-loops")
#pragma G++ optimize("-falign-labels")
#pragma G++ optimize("-fdevirtualize")
#pragma G++ optimize("-fcaller-saves")
#pragma G++ optimize("-fcrossjumping")
#pragma G++ optimize("-fthread-jumps")
#pragma G++ optimize("-funroll-loops")
#pragma G++ optimize("-fwhole-program")
#pragma G++ optimize("-freorder-blocks")
#pragma G++ optimize("-fschedule-insns")
#pragma G++ optimize("inline-functions")
#pragma G++ optimize("-ftree-tail-merge")
#pragma G++ optimize("-fschedule-insns2")
#pragma G++ optimize("-fstrict-aliasing")
#pragma G++ optimize("-fstrict-overflow")
#pragma G++ optimize("-falign-functions")
#pragma G++ optimize("-fcse-skip-blocks")
#pragma G++ optimize("-fcse-follow-jumps")
#pragma G++ optimize("-fsched-interblock")
#pragma G++ optimize("-fpartial-inlining")
#pragma G++ optimize("no-stack-protector")
#pragma G++ optimize("-freorder-functions")
#pragma G++ optimize("-findirect-inlining")
#pragma G++ optimize("-frerun-cse-after-loop")
#pragma G++ optimize("inline-small-functions")
#pragma G++ optimize("-finline-small-functions")
#pragma G++ optimize("-ftree-switch-conversion")
#pragma G++ optimize("-foptimize-sibling-calls")
#pragma G++ optimize("-fexpensive-optimizations")
#pragma G++ optimize("-funsafe-loop-optimizations")
#pragma G++ optimize("inline-functions-called-once")
#pragma G++ optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
#define pb push_back 
#define ott(i,l,r) for (int i = l; i <= r; i ++)
#define tto(i,l,r) for (int i = r; i >= l; i --)
using namespace std;
using ll = long long;
int read () {
	int x = 0; bool f = 0; char c = getchar ();
	while (!isdigit (c)) f |= (c == '-'), c = getchar ();
	while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
	if (f) x = -x; return x;
}
const int N = 3e5 + 1;
int n, m, q, idx, B;
ll res;
vector <int> e[N], E[N];
int up[N], dn[N];
int dfn[N], dep[N], fa[N];
int lg[N << 1], f[N << 1][20];
char ch[N];
void dfs0 (int u) {
	f[dfn[u] = ++ idx][0] = u, dep[u] = dep[fa[u]] + 1;
	for (int v : e[u]) {
		dfs0 (v);
		f[++ idx][0] = u;
	}
	return ;
}
int lca (int x, int y) {
	x = dfn[x], y = dfn[y];
	if (x > y) swap (x, y);
	int z = lg[y - x + 1], f1 = f[x][z], f2 = f[y - (1 << z) + 1][z];
	return dep[f1] < dep[f2] ? f1 : f2;
}
struct OPT {
	int x; char c;
} a[N];
struct BLOCK {
	int ac, now, sum;//ac = 'A'count
	int s[1200];
	void ins (int v) {
		if (v >= now) ++ sum;
		if (-m <= v && v <= m) ++ s[v + m];
		return ;
	}
	void upd (int i) {
		if (ch[i] == 'A') ++ ac;
		if (ch[i] == '?') ins (dn[i] - up[i]);
		return ;
	}
	void add (int v) {
		if (v == 1) {
			sum -= s[(now ++) + m];
			res -= 1ll * sum;
		}
		if (v == -1) {
			res += 1ll * sum;
			sum += s[(-- now) + m];
		}
		return ;
	}
	void clear () {
		ac = now = sum = 0;
		ott (i, 0, m + m) s[i] = 0;
		return ;
	}
} b[N];
int id[N], val[N], FA[N];
bool cmp (int x, int y) {
	return dfn[x] < dfn[y];
}
void push (int u, int z) {
	b[z].upd (u);
	for (int v : e[u]) push (v, z);
	return ;
}
int Z, OTH;
void find (int x) {
	if (id[fa[x]]) {
		val[Z = id[x] = ++ idx] = x;
		return ;
	}
	find (fa[x]);
	b[Z].upd (fa[x]);
	for (int v : e[fa[x]]) {
		if (v == x) continue;
		if (!OTH) val[OTH = id[v] = ++ idx] = v;
		push (v, OTH);
	}
	return ;
}
void red (int u) {
	dn[u] = 0;
	for (int v : e[u]) {
		up[v] = up[u] + (ch[u] != 'C');
		red (v);
		dn[u] += dn[v] + (ch[v] != 'A');
	}
	if (ch[u] == 'A') res += 1ll * dn[u];
	if (ch[u] == '?') res += 1ll * max (0, dn[u] - up[u]);
	return ;
}
void cup (int u, int V) {
	for (int v : E[u]) {
		if (val[v] < 0) {
			int tv = -val[v];
			if (ch[tv] == '?') res -= 1ll * max (0, dn[tv] - up[tv]);
			up[tv] += V;
			if (ch[tv] == '?') res += 1ll * max (0, dn[tv] - up[tv]);
		}
		else {
			b[v].add (V);
		}
		cup (v, V);
	}
	return ;
}
void cdn (int u, int V) {
	if (!u) return ;
	if (val[u] < 0) {
		int tu = -val[u];
		if (ch[tu] == '?') res -= 1ll * max (0, dn[tu] - up[tu]);
		dn[tu] += V; if (ch[tu] == 'A') res += 1ll * V;
		if (ch[tu] == '?') res += 1ll * max (0, dn[tu] - up[tu]);
	}
	else {
		b[u].add (-V), res += 1ll * b[u].ac * V;
	}
	cdn (FA[u], V);
	return ;
}
void sol () {
    ott (i, 1, m) val[++ idx] = a[i].x;
    sort (val + 1, val + 1 + idx), idx = unique (val + 1, val + 1 + idx) - val - 1;
    sort (val + 1, val + 1 + idx, cmp);
    ott (i, 2, idx) val[idx + i - 1] = lca (val[i - 1], val[i]); val[idx += idx] = 1;
    sort (val + 1, val + 1 + idx), idx = unique (val + 1, val + 1 + idx) - val - 1;
    ott (i, 1, idx) {
    	id[val[i]] = i;
    	val[i] = -val[i];//区分会修改的点
	}
    ott (i, 2, idx) {
    	if (val[i] > 0) break;
    	if (!id[fa[-val[i]]]) {
    		OTH = Z = 0, find (-val[i]);
    		if (OTH) E[FA[OTH] = i].pb (OTH);
    		E[FA[Z] = id[fa[val[Z]]]].pb (Z), E[FA[i] = Z].pb (i);
		}
		else E[FA[i] = id[fa[-val[i]]]].pb (i);
	}
	ott (i, 1, idx) {
		if (val[i] > 0) break;
		OTH = 0; for (int v : e[-val[i]]) {
			if (id[v]) continue;
			if (!OTH) {
				val[OTH = id[v] = ++ idx] = v;
				E[FA[OTH] = i].pb (OTH);
			}
			push (v, OTH);
		}
	}
	ott (i, 1, m) {
		int x = a[i].x; char c = a[i].c;
		if (ch[x] != 'C') cup (id[x], -1); if (ch[x] != 'A') cdn (FA[id[x]], -1);
		if (ch[x] == 'A') res -= 1ll * dn[x];
		if (ch[x] == '?') res -= 1ll * max (0, dn[x] - up[x]);
		ch[x] = c;
		if (ch[x] == 'A') res += 1ll * dn[x];
		if (ch[x] == '?') res += 1ll * max (0, dn[x] - up[x]);
		if (ch[x] != 'C') cup (id[x], 1); if (ch[x] != 'A') cdn (FA[id[x]], 1);
		printf ("%lld\n", res);
	}
	ott (i, 1, idx) {
		E[i].clear (), FA[i] = 0;
		if (val[i] < 0) val[i] = -val[i];
		else b[i].clear ();
		id[val[i]] = 0, val[i] = 0;
	}
	m = idx = 0, res = 0; red (1);
	return ;
}
int main () {
	//freopen ("data.in", "r", stdin); freopen ("res.out", "w", stdout);
	n = read (), q = read (), cin >> ch + 1; ott (i, 2, n) e[fa[i] = read ()].pb (i);
	B = (int)sqrt (q); dfs0 (1);
	ott (j, 1, 19) {
		ott (i, 1, idx - (1 << j) + 1) {
			int f1 = f[i][j - 1], f2 = f[i + (1 << j - 1)][j - 1];
			f[i][j] = dep[f1] < dep[f2] ? f1 : f2;
		}
	}
	lg[0] = -1;	ott (i, 1, idx) lg[i] = lg[i >> 1] + 1;
	idx = 0, red (1); ott (i, 1, q) {
		int x = read (); char c = getchar ();
		a[++ m] = {x, c};
		if (i % B == 0 || i == q) sol ();
	}
	return 0;
}

Source code, Language: C++11

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 31696kb

input:

5 3
AC??C
1 2 2 1
1 ?
4 A
2 ?

output:

4
3
3

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 4ms

memory: 33040kb

input:

1000 1000
AC?ACCCCC?CCA??CCCCC?A?AC?C??C?ACCCACC?C?CCC?CACACA???????C?????CC?C?AAAAACCA??AAAACACACA???AACAC?CCC?CAC?AAAACCAC???ACAA??A??A?CA?A?ACACACCAA?ACACA?AC??AC??ACAAACCC??CAA?A???CC?AA??AC???A?CCCC??CACCAACC?AA?C?AAACCCA?AAA??C?CC??CACCACAACCA?AACCC?A?CCC?CC???AA?CACCCAAC??CAA??C?AA??CA???CAAA...

output:

result:

wrong answer 25th lines differ - expected: '2767', found: '2768'