QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#663455#9477. Topological SortrageOfThunder#AC ✓33ms6280kbC++232.0kb2024-10-21 15:41:302024-10-21 15:41:32

Judging History

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

  • [2024-10-21 15:41:32]
  • 评测
  • 测评结果:AC
  • 用时:33ms
  • 内存:6280kb
  • [2024-10-21 15:41:30]
  • 提交

answer

// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = - f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 2e5 + 10, MOD = 998244353;
inline int power(int x, ll y = MOD - 2) {
	int ans = 1;
	for (; y; x = (ll) x * x % MOD, y >>= 1)
		if (y & 1) ans = (ll) ans * x % MOD;
	return ans;
}
int n, a[N], t[N];
void add(int x) {
	for (; x <= n; x += x & -x) t[x]++;
}
int query(int x) {
	int s = 0;
	for (; x; x ^= x & -x) s += t[x];
	return s;
}
long long f[1000001],an=1;
signed main() {
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	read(n);
	F(i, 1, n) {
		read(a[i]);
	}
//	f[0]=1;
//	for(int i=1;i<=500000;i++)
//	{
//		f[i]=(f[i-1]*(power(2,i-1)-1)%MOD*2+f[i-1])%MOD;
//	}
//	for(long long i=1;i<=500000;i++) f[i]=f[i]*power(power(2),i*(i+1)/2)%MOD;
	ll s = 0;
	stack <int> t;
	DF(i, n, 1) {
		s += n - i;
		long long gg=0;
		long long nww=1;
		while (t.size() && a[t.top()] < a[i]) {
			int tt=t.top();
			nww=nww*((power(2,(tt-i-1))-1)%MOD*2+1)%MOD*power(power(2),tt-i)%MOD;
			t.pop();
		}
//		cout<<f[gg]<<" ";
		an=an*nww%MOD;
		t.push(i);
		// if (query(a[i])) s += n - i - 1;
		// else s += n - i;
		// s += max(0, query(a[i]) - 1);
		// add(a[i]);
	}
	an=(an*power(2, s)%MOD+MOD)%MOD;
//	while(t.size()) cout<<t.top()<<" ",t.pop();
	cout << an;
	return 0;
}
/* why?
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5620kb

input:

3
1 3 2

output:

4

result:

ok "4"

Test #2:

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

input:

5
1 2 3 4 5

output:

1024

result:

ok "1024"

Test #3:

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

input:

6
4 2 1 5 6 3

output:

4096

result:

ok "4096"

Test #4:

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

input:

492
397 486 227 395 58 452 172 216 130 181 268 482 85 209 365 104 373 90 260 326 252 96 267 106 102 398 441 41 292 314 12 78 242 353 153 424 179 86 299 228 54 390 73 465 396 349 4 10 451 99 342 250 391 6 323 197 159 47 136 473 392 77 125 362 418 255 291 13 238 339 8 28 413 121 384 157 152 23 221 305...

output:

73428942

result:

ok "73428942"

Test #5:

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

input:

117
114 89 34 77 56 24 36 97 57 75 25 99 51 87 31 53 20 18 71 88 92 11 101 5 105 81 113 110 86 37 79 33 61 13 9 2 48 7 63 3 45 4 74 102 38 30 23 55 115 112 44 76 35 62 10 103 21 72 106 40 68 93 22 66 50 52 17 58 78 95 116 8 91 82 65 1 47 19 15 60 27 80 26 100 6 107 117 98 16 69 83 109 12 96 111 32 2...

output:

973031884

result:

ok "973031884"

Test #6:

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

input:

142
5 91 117 42 103 25 15 68 17 57 6 108 94 139 49 61 118 130 50 36 39 135 53 113 73 16 75 134 37 124 140 93 78 105 20 136 59 48 10 9 126 99 119 1 88 86 38 69 115 62 97 55 3 85 23 82 65 84 106 83 24 31 131 109 44 11 8 33 89 125 141 112 128 122 74 22 123 2 43 129 56 111 87 34 47 100 12 71 120 81 28 2...

output:

689040121

result:

ok "689040121"

Test #7:

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

input:

2
1 2

output:

2

result:

ok "2"

Test #8:

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

input:

2
2 1

output:

1

result:

ok "1"

Test #9:

score: 0
Accepted
time: 33ms
memory: 6240kb

input:

194626
192391 66573 51175 20393 139133 182361 61827 110888 4046 131771 18067 2183 160224 138697 39109 20417 69500 109571 52869 129131 77495 95741 123039 79656 88279 149323 76536 158952 163825 12131 178853 174294 83666 103342 100664 149219 136306 81716 100831 29396 128703 43798 56614 184849 170761 14...

output:

768358540

result:

ok "768358540"

Test #10:

score: 0
Accepted
time: 28ms
memory: 4196kb

input:

160968
160947 4849 31045 8012 36591 12857 147608 10869 130042 51427 115245 84111 63736 84890 113838 132449 78264 122080 149108 37262 48513 10846 72189 77505 32035 103483 23564 51479 41991 82334 117627 43428 73435 61631 138561 135985 70663 54059 43373 79399 126360 114320 15911 898 74743 72917 118342 ...

output:

817724348

result:

ok "817724348"

Test #11:

score: 0
Accepted
time: 19ms
memory: 4260kb

input:

111001
26673 41956 62271 20608 31376 57244 96627 21050 358 38331 27722 39740 731 102706 60567 27528 93333 73599 1241 86518 49179 99721 8859 87696 39278 31105 60999 66188 41513 74527 77815 29823 43087 110 98990 78723 42526 31732 32018 1014 7403 69997 90978 55115 40241 14889 22516 102918 30682 61528 5...

output:

975779120

result:

ok "975779120"

Test #12:

score: 0
Accepted
time: 23ms
memory: 4160kb

input:

136936
37703 45931 8052 128245 66821 76075 66893 81424 116099 28846 49133 19515 107613 76522 54074 125802 23455 80819 65212 44785 118726 40345 36957 88481 82004 105105 135593 123696 16840 31807 103176 39208 58888 76782 38881 116052 74631 127015 21372 68215 97169 103724 104325 79254 100408 34321 8445...

output:

585608213

result:

ok "585608213"

Test #13:

score: 0
Accepted
time: 22ms
memory: 4712kb

input:

200000
4 3 1 2 7 6 5 8 9 16 13 11 10 12 15 14 18 17 21 20 19 22 24 23 25 28 31 32 29 30 27 26 34 36 38 35 33 37 41 40 39 42 43 50 47 46 49 44 48 45 51 54 52 53 60 62 57 59 56 58 55 61 71 64 68 63 72 66 69 65 67 70 76 78 75 77 79 80 73 74 85 86 81 87 82 83 90 88 84 89 92 93 91 97 100 98 95 96 99 101 ...

output:

835319992

result:

ok "835319992"

Test #14:

score: 0
Accepted
time: 31ms
memory: 6000kb

input:

200000
1 45 36 6 64 47 41 63 59 29 28 10 4 15 33 35 18 68 56 31 25 12 22 69 44 55 61 54 16 30 42 39 17 65 60 58 52 9 53 7 8 5 49 57 26 24 46 38 37 21 48 66 32 34 11 50 2 13 62 43 3 23 51 27 67 40 14 19 20 71 70 86 115 107 78 105 76 110 73 80 93 88 72 100 77 108 92 106 85 97 95 81 103 79 84 101 102 7...

output:

806652810

result:

ok "806652810"

Test #15:

score: 0
Accepted
time: 32ms
memory: 6200kb

input:

200000
199997 199999 200000 199998 199995 199994 199996 199993 199987 199989 199986 199992 199988 199991 199990 199985 199976 199982 199979 199980 199984 199983 199977 199978 199981 199972 199973 199975 199974 199968 199969 199970 199971 199965 199961 199958 199967 199960 199966 199962 199959 199963...

output:

634066694

result:

ok "634066694"

Test #16:

score: 0
Accepted
time: 29ms
memory: 5956kb

input:

200000
199988 199987 199997 199990 199994 199995 199999 199992 199993 199998 199991 199996 199989 200000 199971 199930 199970 199965 199972 199950 199977 199951 199945 199976 199960 199947 199982 199962 199936 199955 199985 199956 199949 199942 199952 199938 199940 199981 199935 199944 199946 199969...

output:

545252947

result:

ok "545252947"

Test #17:

score: 0
Accepted
time: 6ms
memory: 5196kb

input:

193839
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

74820210

result:

ok "74820210"

Test #18:

score: 0
Accepted
time: 30ms
memory: 6280kb

input:

196576
196576 196575 196574 196573 196572 196571 196570 196569 196568 196567 196566 196565 196564 196563 196562 196561 196560 196559 196558 196557 196556 196555 196554 196553 196552 196551 196550 196549 196548 196547 196546 196545 196544 196543 196542 196541 196540 196539 196538 196537 196536 196535...

output:

861096285

result:

ok "861096285"

Extra Test:

score: 0
Extra Test Passed