#317296 (C++11) No.318 学学学学学

提出ソース

結果

問題	No.318 学学学学学
ユーザー	rapurasu
提出日時	2019-02-19 03:00:18
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	187 ms / 2,000 ms
コード長	4,291 bytes
コンパイル時間	2,244 ms
コンパイル使用メモリ	182,928 KB
実行使用メモリ	22,032 KB
最終ジャッジ日時	2024-06-22 18:48:50
合計ジャッジ時間	6,836 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	15 ms 12,768 KB
testcase_01	AC	27 ms 14,308 KB
testcase_02	AC	38 ms 14,692 KB
testcase_03	AC	25 ms 13,332 KB
testcase_04	AC	31 ms 13,764 KB
testcase_05	AC	187 ms 22,032 KB
testcase_06	AC	178 ms 17,292 KB
testcase_07	AC	177 ms 16,836 KB
testcase_08	AC	170 ms 15,996 KB
testcase_09	AC	172 ms 15,828 KB
testcase_10	AC	147 ms 14,424 KB
testcase_11	AC	182 ms 21,872 KB
testcase_12	AC	153 ms 17,820 KB
testcase_13	AC	139 ms 16,440 KB
testcase_14	AC	134 ms 16,024 KB
testcase_15	AC	121 ms 15,268 KB
testcase_16	AC	106 ms 14,296 KB
testcase_17	AC	116 ms 17,240 KB
testcase_18	AC	115 ms 17,064 KB
testcase_19	AC	117 ms 17,436 KB
testcase_20	AC	95 ms 15,452 KB
testcase_21	AC	4 ms 12,808 KB
testcase_22	AC	4 ms 12,724 KB
testcase_23	AC	4 ms 12,844 KB
testcase_24	AC	4 ms 12,744 KB
testcase_25	AC	4 ms 11,904 KB
testcase_26	AC	4 ms 12,788 KB
testcase_27	AC	4 ms 13,648 KB
testcase_28	AC	4 ms 12,240 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;

//根ノードを1としているので，
//左の子:k*2
//右の子:k*2+1
//親:floor(k/2)
//となる．
//根ノードを1とすると非再帰が書きやすい(二進数的性質が優れているため)のだが，
//再帰的に書くのであればどちらでも問題ない．
//int maxi[N*2];
//int lazy[N*2];
namespace LST_{
	using RET = LL;//葉の個数
	constexpr int BUF =1048576+20;
	RET t[BUF];
	int ptr=0;
	inline RET* get(const int size){
		ptr+=size;
		return t+ptr-size;
	}
	
}

struct LazySegTree{
	using T=LST_::RET;
	T* maxi;//ノードkに対応する区間の最大値
	T* lazy;//lazy[k]はノードkの配下全体をlazy[k]で塗りつぶすという命令を表す．lazy[k]=NILのときは何もしないと約束する.
	static const T NIL = 1e9+8;//lazyがこの値の時は更新しない
	//2^20=1048576, 2^19= 524288
	//2^18=262144,  2^17= 131072(2のべきでないといけない)
	static const int N = 262144;
	LazySegTree(){
		maxi=LST_::get(2*N);//最大値の配列の確保
		lazy=LST_::get(2*N);//遅延の確保
		//更新用
		REP(i,N+10){
			lazy[i]=NIL;
			maxi[i]=0;
		}
		//加算用
		//REP(i,2*N){
		//	lazy[i]=0;
		//	maxi[i]=0;
		//}
	}
	
	//kをvで塗りつぶす
	void setLazy(int k,T v){
		//更新用
		lazy[k]=v;
		maxi[k]=v;
		//加算用
		//lazy[k]+=v;
		//maxi[k]+=v;
	}
	void push(int k){
		//遅延命令がなにもなければ何もしない
		//更新用
		if(lazy[k]==NIL){
			return;
		}
		//加算用
		//if(lazy[k]==0){
		//	return;
		//}
		setLazy(k*2+0,lazy[k]);
		setLazy(k*2+1,lazy[k]);
		//子に命令を伝搬させたので，命令を空にする
		lazy[k] =NIL;
		//lazy[k]=0;//加算用
	}
	//最大値を求める
	T compar(T a, T b){
		return max(a,b);
		//return min(a,b);最小値を求める場合はこっちを使う
	}
	
	void fix(int k){
		//ノードkに対応する区間の最大値は，「左の子の最大値」と「右の子の最大値」の最大値
		maxi[k]=compar(maxi[k*2],maxi[k*2+1]);
	}
	//区間[queryL,queryR)をvalで塗りつぶす
	void fill(int queryL, int queryR, T val, int k=1,int nodeL =0,int nodeR=N){
		 //クエリ区間とノード区間が交差していないのなら，これ以上，処理する必要はない
		if(nodeR <= queryL || queryR<=nodeL){
			return;
		}
		//ノード区間がクエリ区間に完全に覆われたら，遅延命令をセットして，さっさと帰る
		if(queryL <= nodeL && nodeR<=queryR){
			setLazy(k,val);
			return;
		}
		//ノードが下がる時には命令をpushする
		push(k);
		int nodeM =(nodeL + nodeR) /2;
		fill(queryL,queryR, val, k*2+0,nodeL, nodeM);
		fill(queryL,queryR, val ,k*2+1,nodeM, nodeR);
		//ノードが上がる時には情報をfixする
		fix(k);
	}
	//区間[queryL,queryR)の最大値を求める
	T maximum(int queryL, int queryR, int k=1,int nodeL=0,int nodeR =N){
		//クエリ区間とノード区間が交差していない
		if(nodeR<=queryL||queryR<=nodeL){
			return -(1e15);
		}
		//ノード区間がクエリ区間に完全に覆われた
		if(queryL <= nodeL && nodeR <=queryR){
			return maxi[k];
		}
		//ノードが下がるときは命令をpushする
		push(k);
		int nodeM =(nodeL+nodeR)/2;
		T vl =maximum(queryL,queryR, k*2+0,nodeL,nodeM);
		T vr =maximum(queryL,queryR, k*2+1,nodeM,nodeR);
		return compar(vl,vr);
	}
};




void show(int N,LazySegTree seg){
	REP(i,N){
		int a=seg.maximum(i,i+1);
		/*if(a%2==0){
			cout<<0;
		}else{
			cout<<1;
		}*/
		cout<<a;
		if(i!=N-1)cout<<" ";
	}
	cout<<endl;
}

vector<LL>v[100011];
map<int,int>m;
int a[100001];
int main(){
	int N;
	cin>>N;
	vector<int>w;
	REP(i,N){
		cin>>a[i];
		w.push_back(a[i]);
	}
	sort(w.begin(),w.end());
	w.erase(unique(w.begin(),w.end()),w.end());
	REP(i,w.size()){
		m[w[i]]=i+1;
	}
	LazySegTree seg;
	REP(i,N){
		seg.fill(i,i+1,a[i]);
		v[m[a[i]]].push_back(i);
	}
	REP(i,100011){
		REP(j,v[i].size()){
			if(j!=v[i].size()-1){
				seg.fill(v[i][j],v[i][j+1],w[i-1]);
			}
			seg.fill(v[i][j],v[i][j]+1,w[i-1]);
		}
	}
	show(N,seg);
	return(0);
}

yukicoder

結果

テストケース

ソースコード