QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309269#8133. When Anton Saw This Task He Reacted With 😩ucup-team088#AC ✓439ms71176kbC++179.4kb2024-01-20 16:16:392024-01-20 16:16:40

Judging History

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

  • [2024-01-20 16:16:40]
  • 评测
  • 测评结果:AC
  • 用时:439ms
  • 内存:71176kb
  • [2024-01-20 16:16:39]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
#include<array>
#include<chrono>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
//ll mod = 1;
constexpr ll mod = 998244353;
//constexpr ll mod = 1000000007;
const int mod17 = 1000000007;
const ll INF = (ll)mod17 * mod17;
typedef pair<int, int>P;

#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;

using ld = double;
typedef pair<ld, ld> LDP;
const ld eps = 1e-10;
const ld pi = acosl(-1.0);

template<typename T>
void chmin(T& a, T b) {
	a = min(a, b);
}
template<typename T>
void chmax(T& a, T b) {
	a = max(a, b);
}
template<typename T>
vector<T> vmerge(vector<T>& a, vector<T>& b) {
	vector<T> res;
	int ida = 0, idb = 0;
	while (ida < a.size() || idb < b.size()) {
		if (idb == b.size()) {
			res.push_back(a[ida]); ida++;
		}
		else if (ida == a.size()) {
			res.push_back(b[idb]); idb++;
		}
		else {
			if (a[ida] < b[idb]) {
				res.push_back(a[ida]); ida++;
			}
			else {
				res.push_back(b[idb]); idb++;
			}
		}
	}
	return res;
}
template<typename T>
void cinarray(vector<T>& v) {
	rep(i, v.size())cin >> v[i];
}
template<typename T>
void coutarray(vector<T>& v) {
	rep(i, v.size()) {
		if (i > 0)cout << " "; cout << v[i];
	}
	cout << "\n";
}
ll mod_pow(ll x, ll n, ll m = mod) {
	if (n < 0) {
		ll res = mod_pow(x, -n, m);
		return mod_pow(res, m - 2, m);
	}
	if (abs(x) >= m)x %= m;
	if (x < 0)x += m;
	//if (x == 0)return 0;
	ll res = 1;
	while (n) {
		if (n & 1)res = res * x % m;
		x = x * x % m; n >>= 1;
	}
	return res;
}
//mod should be <2^31
struct modint {
	int n;
	modint() :n(0) { ; }
	modint(ll m) {
		if (m < 0 || mod <= m) {
			m %= mod; if (m < 0)m += mod;
		}
		n = m;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
bool operator<(modint a, modint b) { return a.n < b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= (int)mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += (int)mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, ll n) {
	if (n == 0)return modint(1);
	modint res = (a * a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) { a = a / b; return a; }
const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[a - b];
}

ll gcd(ll a, ll b) {
	a = abs(a); b = abs(b);
	if (a < b)swap(a, b);
	while (b) {
		ll r = a % b; a = b; b = r;
	}
	return a;
}
template<typename T>
void addv(vector<T>& v, int loc, T val) {
	if (loc >= v.size())v.resize(loc + 1, 0);
	v[loc] += val;
}
/*const int mn = 2000005;
bool isp[mn];
vector<int> ps;
void init() {
	fill(isp + 2, isp + mn, true);
	for (int i = 2; i < mn; i++) {
		if (!isp[i])continue;
		ps.push_back(i);
		for (int j = 2 * i; j < mn; j += i) {
			isp[j] = false;
		}
	}
}*/

//[,val)
template<typename T>
auto prev_itr(set<T>& st, T val) {
	auto res = st.lower_bound(val);
	if (res == st.begin())return st.end();
	res--; return res;
}

//[val,)
template<typename T>
auto next_itr(set<T>& st, T val) {
	auto res = st.lower_bound(val);
	return res;
}
using mP = pair<modint, modint>;
mP operator+(mP a, mP b) {
	return { a.first + b.first,a.second + b.second };
}
mP operator+=(mP& a, mP b) {
	a = a + b; return a;
}
mP operator-(mP a, mP b) {
	return { a.first - b.first,a.second - b.second };
}
mP operator-=(mP& a, mP b) {
	a = a - b; return a;
}
LP operator+(LP a, LP b) {
	return { a.first + b.first,a.second + b.second };
}
LP operator+=(LP& a, LP b) {
	a = a + b; return a;
}
LP operator-(LP a, LP b) {
	return { a.first - b.first,a.second - b.second };
}
LP operator-=(LP& a, LP b) {
	a = a - b; return a;
}

mt19937 mt(time(0));

const string drul = "DRUL";
string senw = "SENW";
//DRUL,or SENW
//int dx[4] = { 1,0,-1,0 };
//int dy[4] = { 0,1,0,-1 };

//------------------------------------

template<typename T>
struct SegT {
private:
	int sz; vector<T> node;
	T init_c;
	function<T(T, T)> f;
public:
	SegT() { ; }
	void init(vector<T> v, T _init_c, function<T(T, T)> _f) {
		init_c = _init_c; f = _f;
		int n = v.size();
		sz = 1;
		while (sz < n)sz *= 2;
		node.resize(2 * sz - 1, init_c);
		rep(i, n) {
			node[i + sz - 1] = v[i];
		}
		per(i, sz - 1) {
			node[i] = f(node[2 * i + 1], node[2 * i + 2]);
		}
	}
	void update(int k, T a) {
		k += sz - 1;
		node[k] = a;
		while (k > 0) {
			k = (k - 1) / 2;
			node[k] = f(node[k * 2 + 1], node[k * 2 + 2]);
		}
	}
	T query(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = sz;
		if (r <= a || b <= l)return init_c;
		else if (a <= l && r <= b)return node[k];
		else {
			T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return f(vl, vr);
		}
	}
	T query() {
		return node[0];
	};
};


void solve() {
	using ar = array<modint, 3>;
	using mat = array<ar, 3>;

	function<mat(mat, mat)> f = [&](mat a, mat b) {
		mat res; rep(i, 3)rep(j, 3)res[i][j] = 0;
		rep(i, 3)rep(k, 3)rep(j, 3) {
			res[i][j] += a[i][k] * b[k][j];
		}
		return res;
	};
	auto apf = [&](mat& a, ar b) {
		ar res; rep(i, 3)res[i] = 0;
		rep(i, 3)rep(j, 3)res[i] += a[i][j] * b[j];
		return res;
	};


	mat e;
	rep(i, 3)rep(j, 3) {
		if (i == j)e[i][j] = 1;
		else e[i][j] = 0;
	}

	vector<SegT<mat>> sts;
	vector<ar> lasts;


	int n, q; cin >> n >> q;
	vector<vector<int>> ch(n);
	vector<ar> mem(n);
	vector<bool> isr(n);
	rep(i, n) {
		char typ; cin >> typ;
		if (typ == 'x') {
			int l, r; cin >> l >> r; l--; r--;
			ch[i] = { l,r };
			isr[r] = true;
		}
		else {
			rep(j, 3) {
				int in; cin >> in;
				mem[i][j] = in;
			}
		}
	}
	vector<int> sz(n);
	function<void(int)>initdfs = [&](int id) {
		sz[id] = 1;
		for (int to : ch[id]) {
			initdfs(to);
			sz[id] += sz[to];
		}
	}; initdfs(0);

	
	vector<vector<int>> ids;
	vector<int> trans(n);
	vector<P> par(n);
	auto getmat = [&](int loc) {
		mat m = sts[loc].query();
		ar nex = apf(m, lasts[loc]);
		mat res; rep(i, 3)rep(j, 3)res[i][j] = 0;
		if (!isr[ids[loc][0]]) {
			res[0][1] = -nex[2];
			res[0][2] = nex[1];
			res[1][0] = nex[2];
			res[1][2] = -nex[0];
			res[2][0] = -nex[1];
			res[2][1] = nex[0];
		}
		else {
			res[0][1] = nex[2];
			res[0][2] = -nex[1];
			res[1][0] = -nex[2];
			res[1][2] = nex[0];
			res[2][0] = nex[1];
			res[2][1] = -nex[0];
		}
		return res;
	};
	int tmp = 0;
	function<void(int)> dfs = [&](int id) {
		int cid = tmp; tmp++;
		sts.push_back({});
		lasts.push_back({});
		ids.push_back({});

		vector<int> cs;
		vector<mat> ori;
		int cur = id;
		cs.push_back(cur);
		while (ch[cur].size()) {
			int idl = ch[cur][0];
			int idr = ch[cur][1];
			if (sz[idl] < sz[idr]) {
				cur = idr;
				dfs(idl);
				ori.push_back(getmat(trans[idl]));
				par[idl] = { cid,cs.size() - 1 };
			}
			else {
				cur = idl;
				dfs(idr);
				ori.push_back(getmat(trans[idr]));
				par[idr] = { cid,cs.size() - 1 };
			}
			cs.push_back(cur);
		}
		for (int id : cs)trans[id] = cid;
		ori.push_back(e);
		sts[cid].init(ori, e, f);
		lasts[cid] = mem[cur];
		ids[cid] = cs;
	};
	dfs(0);
	rep(i, q) {
		ar na;
		int v; cin >> v; rep(j, 3) {
			int in; cin >> in;
			na[j] = in;
		}
		v--;
		int loc = trans[v];
		lasts[loc] = na;
		while (loc > 0) {
			mat m = getmat(loc);
			P p = par[ids[loc][0]];
			int k = p.second;
			int nloc = p.first;
			sts[nloc].update(k, m);
			loc = nloc;
		}
		mat m = sts[0].query();
		ar nex = apf(m, lasts[0]);
		rep(j, 3) {
			if (j > 0)cout << " "; cout << nex[j];
		}
		cout << "\n";
	}
}



signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed<<setprecision(10);
	//init_f();
	//init();
	//while(true)
	//expr();
	//int t; cin >> t; rep(i, t)
	solve();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 3
x 2 3
v 1 0 1
x 4 5
v 0 2 1
v 1 1 1
4 1 2 3
5 0 1 1
4 0 2 2

output:

998244351 0 2
1 998244351 998244352
0 0 0

result:

ok 9 numbers

Test #2:

score: 0
Accepted
time: 439ms
memory: 56748kb

input:

199999 100000
x 137025 65661
v 572518668 158967010 74946561
x 129836 192657
x 141948 187810
v 574918069 328924434 141474729
x 143312 111002
x 52772 148497
v 922857701 690080961 651915759
v 656198340 28002884 129579416
v 639893144 265359784 646791226
v 796871409 411409966 598676495
v 882562617 224394...

output:

393120558 773766615 387297348
759959566 981774500 128012497
294611811 980011608 533642029
404379574 745296852 53493560
404565501 828869760 78021156
592494858 647751304 881427733
190018467 515243135 518180555
628180500 509984554 257430135
13737245 352087791 917410487
932051309 366591227 479931477
199...

result:

ok 300000 numbers

Test #3:

score: 0
Accepted
time: 414ms
memory: 56980kb

input:

199999 100000
x 154525 80092
v 450407262 725458410 590777520
x 24720 135901
v 719242117 114943104 186796011
v 382530926 89156744 943939337
x 183376 26042
x 109984 157873
x 151637 150600
x 4115 27454
x 163135 92648
x 16764 33212
v 849210403 945083972 689295397
v 471196117 68587428 225597765
x 24643 5...

output:

677067461 996514296 449166851
810403092 258196842 853459733
410756156 253348518 912664471
327134890 519245783 922528759
317367558 536888537 506214109
484753530 879045782 772404948
422920052 152084658 517340457
1207902 348787162 320821077
776293878 699474926 711114530
871858473 468497588 822120121
24...

result:

ok 300000 numbers

Test #4:

score: 0
Accepted
time: 365ms
memory: 59172kb

input:

199999 100000
x 72889 193806
x 35339 33069
v 314802407 406980523 492377265
x 108307 60027
x 144922 140917
v 328481079 117663280 644171354
v 482028404 951751561 166221217
v 936461869 436114879 421819757
x 152919 99965
x 61168 150607
v 56403640 743462679 134896557
v 24809217 462947115 966139991
v 7828...

output:

23709876 380448367 629159667
760678420 539369190 611778104
114926687 653692915 939877414
674199470 304745735 544123803
953800112 186017361 49200537
327282782 871001677 293980713
588783157 502130649 190564297
102680906 993889016 963478755
510012481 105416897 281770975
811082806 367139818 493674194
32...

result:

ok 300000 numbers

Test #5:

score: 0
Accepted
time: 336ms
memory: 57468kb

input:

199999 100000
x 134204 79203
v 152855933 152545887 271660214
v 393332175 182708769 115884220
v 731792305 965028257 676889584
x 89631 14495
x 142016 85686
v 600051847 172947969 906920949
v 846126215 214556203 657929902
x 125721 133526
x 93179 35713
v 330716449 450417250 611411649
v 114397688 58644961...

output:

139597616 375474977 14619793
889328460 79727434 363703631
397351102 877961602 429046190
588368345 819425899 502148739
520578911 186408072 484373545
997888597 816534316 338411279
334166269 288211584 608252640
509280845 362972392 286415695
363396960 878881251 3658455
711270872 94816531 100279034
48844...

result:

ok 300000 numbers

Test #6:

score: 0
Accepted
time: 328ms
memory: 59160kb

input:

199999 100000
x 29842 60343
x 22382 27649
v 148997533 411153785 529195552
v 831453378 856711025 439562917
x 183061 152107
v 208562249 845550020 248974502
x 8708 152913
v 901332053 480035531 424365358
v 120556946 620074725 884675784
v 493886564 455460926 851190410
x 63346 64739
x 35246 36255
v 762936...

output:

236797322 190218414 70559261
661765898 266356472 481630021
410967670 613729303 804008156
92638320 37926778 82924205
357869883 232766711 579608532
691702082 124868602 187367212
237610689 608489848 581104410
848616732 907873139 859807891
614624615 454674844 673629667
485784731 743926138 168595096
1826...

result:

ok 300000 numbers

Test #7:

score: 0
Accepted
time: 320ms
memory: 60064kb

input:

199999 100000
x 179471 175117
x 189060 178495
x 20142 58065
x 22916 150184
v 704047412 186112247 660817663
v 761554808 199099716 794321264
v 362925435 508140595 251556541
v 65674025 717152823 157775106
v 325965317 977108704 50644678
v 566946741 833186394 771714200
v 996708965 76780827 625429369
v 85...

output:

365258325 105829774 612397830
731509055 576900445 663777200
553518677 415454275 7683807
468131249 577225931 513594285
215590236 861146274 812820392
669985796 229486834 564691763
929231866 520228049 774609748
29950289 569366391 721072115
644573107 513714638 554458153
728007201 423847330 100860143
192...

result:

ok 300000 numbers

Test #8:

score: 0
Accepted
time: 357ms
memory: 58448kb

input:

199999 100000
x 73506 171332
x 135330 187765
v 308206068 679940956 278078069
v 442448744 196158033 738117032
x 194709 115786
v 208526122 936976225 340056181
x 42663 43401
x 55484 199464
v 865443128 131903961 74265613
x 44659 44773
x 32199 18455
v 986118756 284329619 244212114
v 793747964 649179736 4...

output:

429717039 868308596 175018519
966246118 532451840 773132006
457086098 631788280 989689243
550574851 6706768 416615899
285141084 505326489 916518702
457465389 653530244 951605771
614211832 767828057 44273794
698196640 494937773 99337798
718503234 422078037 151379051
20520347 707143833 781787052
24220...

result:

ok 300000 numbers

Test #9:

score: 0
Accepted
time: 335ms
memory: 61052kb

input:

199999 100000
x 109220 170287
v 563361501 367416904 98790213
x 31431 96958
x 99594 159052
x 95382 129615
v 61965807 547448247 405891792
v 443530416 578856323 588763197
v 761021716 795533831 212530056
v 370964907 391812631 255457982
x 49713 153066
x 141543 111694
v 144135957 614962153 284136518
x 416...

output:

433293962 336914247 747368803
992117520 9180464 159616244
483825959 496735833 964507719
912495370 737285784 595438897
467123496 44306423 562070292
903488238 42971643 61415659
269853145 336741491 565138878
926999098 134871683 277614816
644727031 476324825 69621281
984868613 112590560 688626178
657736...

result:

ok 300000 numbers

Test #10:

score: 0
Accepted
time: 2ms
memory: 12096kb

input:

3 1
x 2 3
v 998244352 998244352 998244352
v 0 0 0
3 1 2 0

output:

2 998244352 998244352

result:

ok 3 number(s): "2 998244352 998244352"

Test #11:

score: 0
Accepted
time: 327ms
memory: 60056kb

input:

199999 100000
x 199465 1690
x 70268 106693
v 194793703 729830314 457557419
x 64673 6910
v 755452906 141328541 558160677
v 725017524 158685295 201414156
x 161801 27226
x 181414 47025
v 387724146 819109666 514628998
v 252532326 97757436 828777580
v 200868967 692540096 706977766
v 300419109 2053530 824...

output:

627210517 640945891 400484640
305641486 893058825 99893167
735729088 805595533 283037791
377070714 357962902 336785549
835938680 634694731 22388934
493696932 612552793 516945234
963890355 517530875 48223226
215318080 742583745 379791022
135074745 970450812 921824280
86572382 481696244 728925909
6372...

result:

ok 300000 numbers

Test #12:

score: 0
Accepted
time: 323ms
memory: 71176kb

input:

199999 100000
x 37758 141919
v 148792593 369372129 595139892
x 59335 149367
v 452667329 904801829 628919068
v 160106559 532238331 179544300
v 850489754 705167899 265598880
x 120963 167491
x 92157 46815
v 444945978 987276260 843838004
x 189040 28027
v 889755401 760730228 3237333
x 168907 82672
v 2329...

output:

897185498 177437016 653646802
48860209 883514812 764698776
505088312 585962448 546090395
914246027 540944167 682989725
965835151 803706423 302298107
452996535 714783487 961852197
882717809 425959754 886391042
203667304 454663502 78105722
512196135 727218227 418204527
274934801 270977361 824228740
74...

result:

ok 300000 numbers

Extra Test:

score: 0
Extra Test Passed