第2回 ドワンゴからの挑戦状 予選

Submission #1175832

Source codeソースコード

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

template<class Handler>
struct segtree_lazy{
	using val_t = typename Handler::val_t;
	using opr_t = typename Handler::opr_t;
	int N;
	vector<val_t> val;
	vector<opr_t> lazy;
	segtree_lazy(){}
	segtree_lazy(int n){init(n);}
	segtree_lazy(const vector<val_t>& vc){init(vc);}
	void init(int n){
		N=1;
		while(N<n) N*=2;
		val .assign(N*2,val_t::e);
		lazy.assign(N*2,opr_t::e);
	}
	void init(const vector<val_t>& vc){
		int n = vc.size();
		N=1;
		while(N<n) N*=2;
		val .assign(N*2,val_t::e);
		rep(i,n) val[i+N] = vc[i];
		for(int i=N-1;i>0;i--) val[i] = val[i*2] + val[i*2+1];
		lazy.assign(N*2,opr_t::e);
	}
	val_t realvalue(int k,int l,int r){
//		return Handler::act(lazy[k],val[k]);
		return Handler::act(lazy[k],val[k],k,l,r);
	}

	val_t calc(int a,int b,int l=0,int r=-1,int k=1){	//query_calc
		if(r==-1) r=N;
		if(b<=l||r<=a) return val_t::e;
		if(a<=l&&r<=b) return realvalue(k,l,r);
		propagate(l,r,k);
		val_t ret = calc(a,b,l,(l+r)/2,k*2) + calc(a,b,(l+r)/2,r,k*2+1);
		val[k] = realvalue(k*2,l,(l+r)/2) + realvalue(k*2+1,(l+r)/2,r);
		return ret;

	}
//	val_t calc_leftassoc(){}
	void update(int a,int b,const opr_t &x,int l=0,int r=-1,int k=1){	//query_update
		if(r==-1) r=N;
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){
			Handler::setg2fg(x,lazy[k]);
			return;
		}
		propagate(l,r,k);
		update(a,b,x,l,(l+r)/2,k*2);
		update(a,b,x,(l+r)/2,r,k*2+1);
		val[k] = realvalue(k*2,l,(l+r)/2) + realvalue(k*2+1,(l+r)/2,r);
	}
	void propagate(int l,int r,int k){	//opr_child -> opr_parent * opr_child		parent after child
		Handler::setg2fg(lazy[k],lazy[k*2  ]);
		Handler::setg2fg(lazy[k],lazy[k*2+1]);
		lazy[k] = opr_t::e;
	}

	int getval(int m){
		return calc(m,m+1).x;
	}
	void add(int l,int r,long long v){
//		printf("add %d,%d, +=%lld\n",l,r,v);
		update(l,r,opr_t(true,v));
	}
	void assign(int l,int r,long long v){
		update(l,r,opr_t(false,v));
	}
};

struct handler3{
	using ll = long long;
	/*
		range assign
		range add
		point val

		val_t = int
		opr_t(x) : assign x or add y

		(assign x)(assign y) = (assign x)
		(assign x)(add y) = (assign x)
		(add x)(assign y) = (assign y+x)
		(add x)(add y) = (add x+y)
		(assign or add)が閉じているので、この形をopr_tとして持てば良い.
		区間getがないとかなり考えやすいなあ
		というか、val_t同士の演算がいらなくて、opr_tだけでできてるなこれ

	*/
	struct val_t{
		ll x;
		val_t(){*this = e;}
		val_t(ll x):x(x){}

		const static val_t e;
		val_t operator+(const val_t &r) const {
			return val_t(x+r.x);
		}
		friend ostream& operator<<(ostream& o,const val_t& d){return o<<d.x;}
	};

	struct opr_t{
		bool is_add;
		ll x;
		opr_t(){*this = e;}
		opr_t(bool b,ll x):is_add(b),x(x){}

		const static opr_t e;
		friend ostream& operator<<(ostream& o,const opr_t& d){return o<<(d.is_add?"add":"assign")<<" "<<d.x;}
	};

	static opr_t getfg(const opr_t &f, const opr_t &g){
		if(f.is_add){
			if(g.is_add) return opr_t(true,f.x+g.x);
			else return opr_t(false,f.x+g.x);
		}else{
			return f;
		}
	}
	static void setg2fg(const opr_t &f, opr_t &g){	//g -> fg		f after g
		g = getfg(f,g);
	}
	static val_t act(const opr_t &f, const val_t &v,int k,int l,int r){	//assign f.x -> sum = 
		if(f.is_add) return val_t(v+f.x);
		else return val_t(f.x);
	}
};
const handler3::val_t handler3::val_t::e = val_t(0);
const handler3::opr_t handler3::opr_t::e = opr_t(true,0);	//単位元はadd 0

segtree_lazy<handler3> seg;

int N,L,t[100000],x[100000];

int pos(){
	int ub=L,lb=-1;
	while(ub-lb>1){
		int m=(ub+lb)/2;
		if(seg.getval(m)>=0) ub=m;
		else lb=m;
	}
	return ub;
}

int main(){
	cin>>N>>L;
	L++;
	seg.init(L);
	rep(i,N) cin>>t[i]>>x[i];
	long long sum=0;
	rep(i,N){
		sum+=x[i];
		seg.add(0,x[i],-1);
		seg.add(x[i],L,1);
		// show(seg.lazy);
		// cout<<"seg ";
		// rep(i,L) cout<<seg.getval(i)<<" ";
		// puts("");

		if(i==N||t[i]!=t[i+1]){
			int p=pos();
//			show(p);
			seg.assign(p,L,0);
			// cout<<"seg ";
			// rep(i,L) cout<<seg.getval(i)<<" ";
			// puts("");
		}
	}
	rep(i,L) sum+=seg.getval(i);
	cout<<sum<<endl;
}
 

Submission

Task問題 E - 花火
User nameユーザ名 025_sigma
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 160
Source lengthソースコード長 4839 Byte
File nameファイル名
Exec time実行時間 531 ms
Memory usageメモリ使用量 8704 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
Subtask1 30 / 30 sample_01.txt,sample_02.txt,sample_03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt,subtask1_23.txt,subtask1_24.txt,subtask1_25.txt,subtask1_26.txt,subtask1_27.txt,subtask1_28.txt,subtask1_29.txt,subtask1_30.txt,subtask1_31.txt,subtask1_32.txt,subtask1_33.txt,subtask1_34.txt,subtask1_35.txt,subtask1_36.txt,subtask1_37.txt,subtask1_38.txt,subtask1_39.txt,subtask1_40.txt,subtask1_41.txt,subtask1_42.txt
Subtask2 130 / 130 sample_01.txt,sample_02.txt,sample_03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt,subtask1_23.txt,subtask1_24.txt,subtask1_25.txt,subtask1_26.txt,subtask1_27.txt,subtask1_28.txt,subtask1_29.txt,subtask1_30.txt,subtask1_31.txt,subtask1_32.txt,subtask1_33.txt,subtask1_34.txt,subtask1_35.txt,subtask1_36.txt,subtask1_37.txt,subtask1_38.txt,subtask1_39.txt,subtask1_40.txt,subtask1_41.txt,subtask1_42.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt,subtask2_13.txt,subtask2_14.txt,subtask2_15.txt,subtask2_16.txt,subtask2_17.txt,subtask2_18.txt,subtask2_19.txt,subtask2_20.txt,subtask2_21.txt,subtask2_22.txt,subtask2_23.txt,subtask2_24.txt,subtask2_25.txt,subtask2_26.txt,subtask2_27.txt,subtask2_28.txt,subtask2_29.txt,subtask2_30.txt,subtask2_31.txt,subtask2_32.txt,subtask2_33.txt,subtask2_34.txt,subtask2_35.txt,subtask2_36.txt,subtask2_37.txt,subtask2_38.txt,subtask2_39.txt,subtask2_40.txt,subtask2_41.txt,subtask2_42.txt,subtask2_43.txt,subtask2_44.txt,subtask2_45.txt,subtask2_46.txt,subtask2_47.txt,subtask2_48.txt,subtask2_49.txt,subtask2_50.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 6 ms 384 KB
subtask1_02.txt AC 6 ms 384 KB
subtask1_03.txt AC 6 ms 384 KB
subtask1_04.txt AC 6 ms 384 KB
subtask1_05.txt AC 2 ms 256 KB
subtask1_06.txt AC 2 ms 256 KB
subtask1_07.txt AC 3 ms 256 KB
subtask1_08.txt AC 4 ms 256 KB
subtask1_09.txt AC 3 ms 384 KB
subtask1_10.txt AC 3 ms 384 KB
subtask1_11.txt AC 3 ms 384 KB
subtask1_12.txt AC 4 ms 384 KB
subtask1_13.txt AC 2 ms 256 KB
subtask1_14.txt AC 2 ms 256 KB
subtask1_15.txt AC 2 ms 256 KB
subtask1_16.txt AC 3 ms 256 KB
subtask1_17.txt AC 6 ms 384 KB
subtask1_18.txt AC 6 ms 384 KB
subtask1_19.txt AC 6 ms 384 KB
subtask1_20.txt AC 6 ms 384 KB
subtask1_21.txt AC 3 ms 384 KB
subtask1_22.txt AC 4 ms 384 KB
subtask1_23.txt AC 5 ms 384 KB
subtask1_24.txt AC 6 ms 384 KB
subtask1_25.txt AC 3 ms 256 KB
subtask1_26.txt AC 3 ms 256 KB
subtask1_27.txt AC 7 ms 384 KB
subtask1_28.txt AC 3 ms 384 KB
subtask1_29.txt AC 2 ms 256 KB
subtask1_30.txt AC 2 ms 256 KB
subtask1_31.txt AC 6 ms 384 KB
subtask1_32.txt AC 7 ms 384 KB
subtask1_33.txt AC 4 ms 384 KB
subtask1_34.txt AC 6 ms 384 KB
subtask1_35.txt AC 3 ms 384 KB
subtask1_36.txt AC 6 ms 384 KB
subtask1_37.txt AC 1 ms 256 KB
subtask1_38.txt AC 2 ms 384 KB
subtask1_39.txt AC 1 ms 256 KB
subtask1_40.txt AC 2 ms 384 KB
subtask1_41.txt AC 1 ms 256 KB
subtask1_42.txt AC 2 ms 384 KB
subtask2_01.txt AC 482 ms 7168 KB
subtask2_02.txt AC 477 ms 7168 KB
subtask2_03.txt AC 482 ms 7168 KB
subtask2_04.txt AC 485 ms 7168 KB
subtask2_05.txt AC 471 ms 7168 KB
subtask2_06.txt AC 365 ms 7040 KB
subtask2_07.txt AC 242 ms 3712 KB
subtask2_08.txt AC 137 ms 3584 KB
subtask2_09.txt AC 59 ms 1024 KB
subtask2_10.txt AC 68 ms 1024 KB
subtask2_11.txt AC 90 ms 1024 KB
subtask2_12.txt AC 128 ms 1024 KB
subtask2_13.txt AC 312 ms 1792 KB
subtask2_14.txt AC 139 ms 7168 KB
subtask2_15.txt AC 140 ms 7168 KB
subtask2_16.txt AC 146 ms 7168 KB
subtask2_17.txt AC 155 ms 7168 KB
subtask2_18.txt AC 213 ms 7168 KB
subtask2_19.txt AC 37 ms 1024 KB
subtask2_20.txt AC 43 ms 1024 KB
subtask2_21.txt AC 53 ms 1024 KB
subtask2_22.txt AC 64 ms 1024 KB
subtask2_23.txt AC 140 ms 1792 KB
subtask2_24.txt AC 384 ms 8704 KB
subtask2_25.txt AC 387 ms 7168 KB
subtask2_26.txt AC 396 ms 7168 KB
subtask2_27.txt AC 403 ms 7168 KB
subtask2_28.txt AC 447 ms 7168 KB
subtask2_29.txt AC 134 ms 7168 KB
subtask2_30.txt AC 147 ms 7168 KB
subtask2_31.txt AC 156 ms 7168 KB
subtask2_32.txt AC 416 ms 7168 KB
subtask2_33.txt AC 423 ms 7168 KB
subtask2_34.txt AC 150 ms 7168 KB
subtask2_35.txt AC 78 ms 1024 KB
subtask2_36.txt AC 104 ms 1024 KB
subtask2_37.txt AC 272 ms 1792 KB
subtask2_38.txt AC 511 ms 7168 KB
subtask2_39.txt AC 138 ms 7168 KB
subtask2_40.txt AC 39 ms 1024 KB
subtask2_41.txt AC 60 ms 1024 KB
subtask2_42.txt AC 531 ms 7168 KB
subtask2_43.txt AC 510 ms 7168 KB
subtask2_44.txt AC 160 ms 7168 KB
subtask2_45.txt AC 452 ms 7168 KB
subtask2_46.txt AC 98 ms 7168 KB
subtask2_47.txt AC 455 ms 7168 KB
subtask2_48.txt AC 25 ms 6400 KB
subtask2_49.txt AC 1 ms 256 KB
subtask2_50.txt AC 25 ms 6400 KB