QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106198#6229. 排列xiaoyaowudi50 215ms11952kbC++142.5kb2023-05-16 21:21:392023-05-16 21:21: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-05-16 21:21:41]
  • 评测
  • 测评结果:50
  • 用时:215ms
  • 内存:11952kb
  • [2023-05-16 21:21:39]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <numeric>
constexpr int N(200010),inf(1.01e9);
namespace T
{
	struct _z
	{
		int mn,mnc,tg;
	}z[N<<2];
	void add(int u,int v)
	{
		z[u].mn+=v;z[u].tg+=v;
	}
	void pd(int u)
	{
		if(z[u].tg) add(u<<1,z[u].tg),add(u<<1|1,z[u].tg),z[u].tg=0;
	}
	void pu(int u)
	{
		if(z[u<<1].mn<z[u<<1|1].mn) z[u].mn=z[u<<1].mn,z[u].mnc=z[u<<1].mnc;
		else if(z[u<<1].mn>z[u<<1|1].mn) z[u].mn=z[u<<1|1].mn,z[u].mnc=z[u<<1|1].mnc;
		else z[u].mn=z[u<<1].mn,z[u].mnc=z[u<<1].mnc+z[u<<1|1].mnc;
	}
	void build(int u,int cl,int cr)
	{
		if(cl==cr){z[u].mn=inf;z[u].mnc=1;return;}int mid((cl+cr)>>1);
		build(u<<1,cl,mid);build(u<<1|1,mid+1,cr);pu(u);
	}
	void upd(int u,int cl,int cr,int ql,int qr,int v)
	{
		if(cl>=ql && cr<=qr){add(u,v);return;}else if(cl!=cr) pd(u);int mid((cl+cr)>>1);
		if(ql<=mid) upd(u<<1,cl,mid,ql,qr,v);if(qr>mid) upd(u<<1|1,mid+1,cr,ql,qr,v);pu(u);
	}
}
long long slv(int a[],int n)
{
	T::build(1,1,n);static int smx[N],smn[N];int tmx(0),tmn(0);
	long long ans(0);
	for(int i(1);i<=n;++i)
	{
		//mx-mn+l
		while(tmn && a[smn[tmn]]>a[i])
		{
			T::upd(1,1,n,smn[tmn-1]+1,smn[tmn],a[smn[tmn]]);
			--tmn;
		}
		smn[++tmn]=i;
		T::upd(1,1,n,smn[tmn-1]+1,smn[tmn],-a[smn[tmn]]);
		while(tmx && a[smx[tmx]]<a[i])
		{
			T::upd(1,1,n,smx[tmx-1]+1,smx[tmx],-a[smx[tmx]]);
			--tmx;
		}
		smx[++tmx]=i;
		T::upd(1,1,n,smx[tmx-1]+1,smx[tmx],a[smx[tmx]]);
		T::upd(1,1,n,i,i,-inf+i);
		// std::cerr<<T::z[1].mn<<" "<<T::z[1].mnc<<std::endl;
		if(T::z[1].mn==i) ans+=T::z[1].mnc;
	}
	return ans;
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n,k;std::cin>>n>>k;
	static int a[N],vs[N],b[N];for(int i(1);i<=k;++i) std::cin>>a[i],vs[i]=a[i];std::sort(vs+1,vs+k+1);
	for(int i(1);i<=k;++i) b[i]=std::lower_bound(vs+1,vs+k+1,a[i])-vs;
	if(!k) std::iota(a+1,a+n+1,1);
	else
	{
		int pos(k);
		vs[0]=0;vs[k+1]=n+1;int bl(b[k]),br(b[k]),tl(b[k]),tr(b[k]);
		auto radd=[&](int r,int l)->void{for(int i(r);i>=l;--i) a[++pos]=i;};
		auto add=[&](int l,int r)->void{for(int i(l);i<=r;++i) a[++pos]=i;};
		auto chg=[&]()->void
		{
			if(tl>bl) radd(vs[tl]-1,vs[tl-1]+1);
			for(int i(tr);i<br;++i) add(vs[i]+1,vs[i+1]-1);
			for(int i(tl-1);i>bl;--i) radd(vs[i]-1,vs[i-1]+1);
			tl=bl;tr=br;
		};
		for(int i(k-1);i;--i)
		{
			bl=std::min(bl,b[i]),br=std::min(br,b[i]);
			if(br-bl==k-i)
			{
				chg();
			}
		}
		bl=0;br=n+1;
		chg();
		std::cout<<slv(a,n)<<"\n";
		for(int i(1);i<=n;++i) std::cout<<a[i]<<(" \n"[i==n]);
	}
	return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 2ms
memory: 3220kb

input:

10 9
2 5 10 8 1 4 9 7 6

output:

12
2 5 10 8 1 4 9 7 6 3

result:

ok correct!

Test #2:

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

input:

10 6
4 3 2 1 5 7

output:

32
4 3 2 1 5 7 6 8 9 10

result:

ok correct!

Test #3:

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

input:

10 4
10 5 7 8

output:

30
10 5 7 8 9 6 4 3 2 1

result:

ok correct!

Test #4:

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

input:

9 3
2 3 4

output:

38
2 3 4 5 6 7 8 9 1

result:

ok correct!

Subtask #2:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 1ms
memory: 3424kb

input:

20 14
6 1 4 3 2 10 5 20 17 16 13 18 15 12

output:

33
6 1 4 3 2 10 5 20 17 16 13 18 15 12 11 14 19 9 8 7

result:

wrong answer your plan is not optimal

Subtask #3:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 2ms
memory: 3400kb

input:

22 20
3 19 17 5 7 12 15 22 10 13 11 8 2 9 6 14 16 20 4 1

output:

23
3 19 17 5 7 12 15 22 10 13 11 8 2 9 6 14 16 20 4 1 18 21

result:

ok correct!

Test #8:

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

input:

22 14
3 18 12 11 7 1 8 4 14 9 22 21 16 5

output:

27
3 18 12 11 7 1 8 4 14 9 22 21 16 5 6 10 13 15 17 19 20 2

result:

ok correct!

Subtask #4:

score: 10
Accepted

Test #9:

score: 10
Accepted
time: 134ms
memory: 11104kb

input:

199899 1
79400

output:

10412404949
79400 79399 79398 79397 79396 79395 79394 79393 79392 79391 79390 79389 79388 79387 79386 79385 79384 79383 79382 79381 79380 79379 79378 79377 79376 79375 79374 79373 79372 79371 79370 79369 79368 79367 79366 79365 79364 79363 79362 79361 79360 79359 79358 79357 79356 79355 79354 79353 ...

result:

ok correct!

Subtask #5:

score: 10
Accepted

Test #10:

score: 10
Accepted
time: 195ms
memory: 11816kb

input:

191393 191393
32224 3810 113151 150094 136298 14214 128374 5493 40926 95388 13836 108772 80691 142140 98735 77447 47803 161246 117751 68781 68971 47977 96955 84464 105119 76918 59979 19121 179774 121202 185018 68697 26220 118151 188665 166116 184189 124353 23802 62039 22066 142966 171539 104019 1189...

output:

191398
32224 3810 113151 150094 136298 14214 128374 5493 40926 95388 13836 108772 80691 142140 98735 77447 47803 161246 117751 68781 68971 47977 96955 84464 105119 76918 59979 19121 179774 121202 185018 68697 26220 118151 188665 166116 184189 124353 23802 62039 22066 142966 171539 104019 118900 2254...

result:

ok correct!

Test #11:

score: 0
Accepted
time: 191ms
memory: 11952kb

input:

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

output:

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

result:

ok correct!

Subtask #6:

score: 10
Accepted

Test #12:

score: 10
Accepted
time: 205ms
memory: 11636kb

input:

185493 185493
164138 100544 43516 166466 20210 73092 6885 134912 135326 146721 166053 126249 173180 143077 7740 63990 108333 144740 79182 183947 95106 159595 97281 77456 17553 108730 7747 128355 70374 68823 126350 73005 89833 130930 104817 88271 37412 5136 92049 7100 100916 103685 27328 98227 130349...

output:

185496
164138 100544 43516 166466 20210 73092 6885 134912 135326 146721 166053 126249 173180 143077 7740 63990 108333 144740 79182 183947 95106 159595 97281 77456 17553 108730 7747 128355 70374 68823 126350 73005 89833 130930 104817 88271 37412 5136 92049 7100 100916 103685 27328 98227 130349 18526 ...

result:

ok correct!

Test #13:

score: 0
Accepted
time: 176ms
memory: 11732kb

input:

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

output:

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

result:

ok correct!

Subtask #7:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 83ms
memory: 7328kb

input:

94962 47652
17 10 11 21 5 12 20 1 13 19 66 114 38 79 83 49 108 104 112 94 44 24 63 105 67 85 70 100 73 39 72 91 96 71 99 28 88 95 106 55 42 65 110 60 97 35 81 76 54 47 141 130 172 189 137 121 171 183 180 196 166 147 133 194 175 165 193 144 119 146 205 122 145 118 149 126 206 199 138 195 207 129 148 ...

output:

147769
17 10 11 21 5 12 20 1 13 19 66 114 38 79 83 49 108 104 112 94 44 24 63 105 67 85 70 100 73 39 72 91 96 71 99 28 88 95 106 55 42 65 110 60 97 35 81 76 54 47 141 130 172 189 137 121 171 183 180 196 166 147 133 194 175 165 193 144 119 146 205 122 145 118 149 126 206 199 138 195 207 129 148 188 1...

result:

wrong answer your plan is not optimal

Subtask #8:

score: 0
Wrong Answer

Test #15:

score: 0
Wrong Answer
time: 186ms
memory: 11312kb

input:

200000 70130
3 6 13 15 5 76 59 104 89 42 60 73 51 115 46 105 26 31 45 116 35 108 111 88 41 50 91 32 48 69 20 114 87 29 117 53 74 96 19 94 34 55 18 72 100 170 147 121 132 169 122 171 160 128 129 164 123 124 168 138 120 153 139 142 173 141 133 148 126 125 174 175 190 198 183 197 178 192 185 176 193 21...

output:

446896
3 6 13 15 5 76 59 104 89 42 60 73 51 115 46 105 26 31 45 116 35 108 111 88 41 50 91 32 48 69 20 114 87 29 117 53 74 96 19 94 34 55 18 72 100 170 147 121 132 169 122 171 160 128 129 164 123 124 168 138 120 153 139 142 173 141 133 148 126 125 174 175 190 198 183 197 178 192 185 176 193 219 202 ...

result:

wrong answer your plan is not optimal

Subtask #9:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 183ms
memory: 11580kb

input:

200000 111432
12 35 21 17 9 43 25 36 47 38 10 42 28 13 32 24 3 46 26 48 49 5 7 34 27 50 37 1 40 53 54 52 68 107 82 101 99 74 79 88 104 96 67 100 94 80 56 66 105 91 102 61 55 106 57 86 87 70 76 75 65 71 89 58 112 110 150 111 132 153 137 141 152 114 122 125 113 146 121 118 115 133 171 205 199 226 176 ...

output:

279556
12 35 21 17 9 43 25 36 47 38 10 42 28 13 32 24 3 46 26 48 49 5 7 34 27 50 37 1 40 53 54 52 68 107 82 101 99 74 79 88 104 96 67 100 94 80 56 66 105 91 102 61 55 106 57 86 87 70 76 75 65 71 89 58 112 110 150 111 132 153 137 141 152 114 122 125 113 146 121 118 115 133 171 205 199 226 176 202 214...

result:

wrong answer your plan is not optimal

Subtask #10:

score: 0
Wrong Answer

Test #18:

score: 10
Accepted
time: 194ms
memory: 11872kb

input:

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

output:

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

result:

ok correct!

Test #19:

score: -10
Wrong Answer
time: 215ms
memory: 11836kb

input:

196542 192884
4015 68810 47545 70278 196343 25868 16040 103198 150508 130222 192293 1148 88773 150912 49343 132154 140164 193876 122474 117922 173775 56014 184072 109551 52544 117341 77408 122145 55476 176029 2985 137183 77861 12484 108489 44578 134648 87137 74111 3074 81632 81673 191887 76403 51555...

output:

196637
4015 68810 47545 70278 196343 25868 16040 103198 150508 130222 192293 1148 88773 150912 49343 132154 140164 193876 122474 117922 173775 56014 184072 109551 52544 117341 77408 122145 55476 176029 2985 137183 77861 12484 108489 44578 134648 87137 74111 3074 81632 81673 191887 76403 51555 17946 ...

result:

wrong answer your plan is not optimal