提出 #69680268

ソースコード 拡げる

#include<iostream>
#include<queue>
#define lc (u<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define Lc lc,l,mid
#define Rc rc,mid+1,r
#define U 1,1,n
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=5e5+10;
int n,k,rk,p[N],r[N];
priority_queue <int> q;
struct sgmtt
{
	int w[N<<2],pos[N<<2];
	void pushup(int u)
	{
		if(w[lc]>w[rc]) w[u]=w[lc],pos[u]=pos[lc];
		else w[u]=w[rc],pos[u]=pos[rc];
	}
	void build(int u,int l,int r)
	{
		if(l==r) {cin>>p[l],w[u]=p[l],pos[u]=l; return;}
		build(Lc),build(Rc),pushup(u);
	}
	void change(int u,int l,int r,int p)
	{
		if(l==r) {w[u]=0; return;}
		if(p<=mid) change(Lc,p);
		else change(Rc,p);
		pushup(u); 
	}
	pii query(int u,int l,int r,int L,int R)
	{
		if(l>=L&&r<=R) return {w[u],pos[u]};
		pii tr={-1,-1};
		if(L<=mid) tr=query(Lc,L,R);
		if(R>mid)
		{
			pii rr=query(Rc,L,R);
			if(rr.fi>tr.fi) tr=rr;
		}
		return tr;
	}
}T;
void chk(int i) {if(T.query(U,max(1,i-k+1),min(n,i+k-1)).fi==p[i]) q.push(i);}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k,T.build(U),rk=n;
	for(int i=1;i<=n;i++) chk(i);
	while(q.size())
	{
		int i=q.top(); q.pop(),r[i]=rk--,T.change(U,i);
		if(k>1&&i>1) chk(T.query(U,max(1,i-k+1),i-1).se);
		if(k>1&&i<n) chk(T.query(U,i+1,min(n,i+k-1)).se); 
	}
	for(int i=1;i<=n;i++) cout<<r[i]<<'\n';
	return 0;
}

提出情報

提出日時
問題 F - Wide Swap
ユーザ KSCD_
言語 C++ 20 (gcc 12.2)
得点 2000
コード長 1421 Byte
結果 AC
実行時間 776 ms
メモリ 18008 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 2000 / 2000
結果
AC × 3
AC × 94
セット名 テストケース
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, 069.txt, 070.txt, 071.txt, 072.txt, 073.txt, 074.txt, 075.txt, 076.txt, 077.txt, 078.txt, 079.txt, 080.txt, 081.txt, 082.txt, 083.txt, 084.txt, 085.txt, 086.txt, 087.txt, 088.txt, 089.txt, 090.txt, sample-01.txt, sample-02.txt, sample-03.txt
ケース名 結果 実行時間 メモリ
000.txt AC 1 ms 3480 KiB
001.txt AC 1 ms 3548 KiB
002.txt AC 1 ms 3508 KiB
003.txt AC 1 ms 3556 KiB
004.txt AC 1 ms 3488 KiB
005.txt AC 1 ms 3372 KiB
006.txt AC 1 ms 3420 KiB
007.txt AC 1 ms 3492 KiB
008.txt AC 1 ms 3580 KiB
009.txt AC 2 ms 3552 KiB
010.txt AC 3 ms 3608 KiB
011.txt AC 2 ms 3640 KiB
012.txt AC 2 ms 3500 KiB
013.txt AC 3 ms 3544 KiB
014.txt AC 3 ms 3644 KiB
015.txt AC 3 ms 3640 KiB
016.txt AC 3 ms 3548 KiB
017.txt AC 2 ms 3552 KiB
018.txt AC 2 ms 3548 KiB
019.txt AC 2 ms 3512 KiB
020.txt AC 1 ms 3528 KiB
021.txt AC 1 ms 3508 KiB
022.txt AC 2 ms 3556 KiB
023.txt AC 2 ms 3548 KiB
024.txt AC 2 ms 3552 KiB
025.txt AC 2 ms 3508 KiB
026.txt AC 3 ms 3424 KiB
027.txt AC 2 ms 3604 KiB
028.txt AC 2 ms 3464 KiB
029.txt AC 1 ms 3560 KiB
030.txt AC 2 ms 3696 KiB
031.txt AC 2 ms 3560 KiB
032.txt AC 2 ms 3476 KiB
033.txt AC 2 ms 3608 KiB
034.txt AC 2 ms 3692 KiB
035.txt AC 2 ms 3548 KiB
036.txt AC 2 ms 3696 KiB
037.txt AC 2 ms 3644 KiB
038.txt AC 2 ms 3640 KiB
039.txt AC 294 ms 16756 KiB
040.txt AC 524 ms 15988 KiB
041.txt AC 776 ms 15908 KiB
042.txt AC 719 ms 15908 KiB
043.txt AC 771 ms 15948 KiB
044.txt AC 513 ms 15896 KiB
045.txt AC 364 ms 16100 KiB
046.txt AC 689 ms 15916 KiB
047.txt AC 732 ms 15940 KiB
048.txt AC 417 ms 15972 KiB
049.txt AC 171 ms 9168 KiB
050.txt AC 385 ms 13936 KiB
051.txt AC 270 ms 9464 KiB
052.txt AC 692 ms 15224 KiB
053.txt AC 29 ms 6448 KiB
054.txt AC 473 ms 14280 KiB
055.txt AC 3 ms 3680 KiB
056.txt AC 52 ms 4960 KiB
057.txt AC 237 ms 9500 KiB
058.txt AC 71 ms 6204 KiB
059.txt AC 150 ms 18008 KiB
060.txt AC 330 ms 15956 KiB
061.txt AC 294 ms 16700 KiB
062.txt AC 334 ms 15948 KiB
063.txt AC 301 ms 16464 KiB
064.txt AC 332 ms 15908 KiB
065.txt AC 312 ms 16320 KiB
066.txt AC 333 ms 15944 KiB
067.txt AC 319 ms 16268 KiB
068.txt AC 336 ms 15932 KiB
069.txt AC 418 ms 16012 KiB
070.txt AC 438 ms 15904 KiB
071.txt AC 434 ms 15920 KiB
072.txt AC 298 ms 16444 KiB
073.txt AC 449 ms 15960 KiB
074.txt AC 292 ms 16740 KiB
075.txt AC 488 ms 15908 KiB
076.txt AC 481 ms 16004 KiB
077.txt AC 461 ms 16000 KiB
078.txt AC 449 ms 15920 KiB
079.txt AC 98 ms 8824 KiB
080.txt AC 17 ms 4184 KiB
081.txt AC 30 ms 4792 KiB
082.txt AC 227 ms 9488 KiB
083.txt AC 55 ms 6216 KiB
084.txt AC 64 ms 6240 KiB
085.txt AC 57 ms 6048 KiB
086.txt AC 14 ms 4164 KiB
087.txt AC 125 ms 8708 KiB
088.txt AC 59 ms 6376 KiB
089.txt AC 142 ms 17980 KiB
090.txt AC 369 ms 15900 KiB
sample-01.txt AC 1 ms 3424 KiB
sample-02.txt AC 1 ms 3640 KiB
sample-03.txt AC 1 ms 3484 KiB