#523650 (C++14) No.1216 灯籠流し/Lanterns

• 問題: No.1216 灯籠流し/Lanterns
• ユーザー: autumn-eel
• 提出日時: 2020-08-02 16:25:23
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,477 ms / 4,500 ms
• コード長: 3,625 bytes
• コンパイル時間: 2,442 ms
• コンパイル使用メモリ: 191,316 KB
• 実行使用メモリ: 227,980 KB
• 最終ジャッジ日時: 2024-11-14 18:01:04
• 合計ジャッジ時間: 23,307 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	7 ms; 19,284 KB
testcase_01	AC	8 ms; 19,384 KB
testcase_02	AC	7 ms; 19,280 KB
testcase_03	AC	7 ms; 19,536 KB
testcase_04	AC	35 ms; 21,888 KB
testcase_05	AC	287 ms; 218,616 KB
testcase_06	AC	38 ms; 37,604 KB
testcase_07	AC	274 ms; 217,280 KB
testcase_08	AC	247 ms; 202,436 KB
testcase_09	AC	132 ms; 108,656 KB
testcase_10	AC	138 ms; 118,788 KB
testcase_11	AC	78 ms; 57,812 KB
testcase_12	AC	33 ms; 17,792 KB
testcase_13	AC	98 ms; 60,376 KB
testcase_14	AC	64 ms; 35,040 KB
testcase_15	AC	110 ms; 53,192 KB
testcase_16	AC	108 ms; 43,520 KB
testcase_17	AC	461 ms; 191,316 KB
testcase_18	AC	125 ms; 60,820 KB
testcase_19	AC	519 ms; 222,336 KB
testcase_20	AC	261 ms; 111,780 KB
testcase_21	AC	138 ms; 65,264 KB
testcase_22	AC	399 ms; 194,220 KB
testcase_23	AC	54 ms; 21,632 KB
testcase_24	AC	36 ms; 35,776 KB
testcase_25	AC	24 ms; 24,320 KB
testcase_26	AC	140 ms; 124,064 KB
testcase_27	AC	66 ms; 45,824 KB
testcase_28	AC	57 ms; 30,336 KB
testcase_29	AC	98 ms; 58,800 KB
testcase_30	AC	119 ms; 89,356 KB
testcase_31	AC	197 ms; 163,180 KB
testcase_32	AC	125 ms; 80,052 KB
testcase_33	AC	48 ms; 29,824 KB
testcase_34	AC	307 ms; 224,688 KB
testcase_35	AC	1,202 ms; 226,844 KB
testcase_36	AC	1,237 ms; 227,980 KB
testcase_37	AC	126 ms; 23,852 KB
testcase_38	AC	528 ms; 224,052 KB
testcase_39	AC	1,477 ms; 224,056 KB
testcase_40	AC	1,241 ms; 226,772 KB
testcase_41	AC	1,204 ms; 226,764 KB
testcase_42	AC	1,248 ms; 226,772 KB
testcase_43	AC	1,264 ms; 226,904 KB
testcase_44	AC	1,261 ms; 227,152 KB
testcase_45	AC	508 ms; 226,648 KB
testcase_46	AC	512 ms; 227,020 KB
testcase_47	AC	522 ms; 226,008 KB
testcase_48	AC	516 ms; 226,280 KB
testcase_49	AC	508 ms; 226,268 KB

ソースコード

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;

struct BIT2D{
	vector<vector<int>>bit;
	BIT2D(){}
	BIT2D(int n,int m){
		bit=vector<vector<int>>(n+10,vector<int>(m+10));
	}
	void add(int a,int b,int val){
		for(int x=a+1;x<bit.size();x+=x&-x){
			for(int y=b+1;y<bit[x].size();y+=y&-y){
				bit[x][y]+=val;
			}
		}
	}
	int sum(int a,int b){
		int res=0;
		for(int x=a+1;x;x-=x&-x){
			for(int y=b+1;y;y-=y&-y){
				res+=bit[x][y];
			}
		}
		return res;
	}
};

vector<P>E[60000];
ll d[60000];               //深さ

int vid[60000],rev[60000]; //Euler Tour上の頂点の順番
int cl[60000],cr[60000];   //部分木に対応する区間

int node_cnt;

void dfs(int v,int p){
	cl[v]=node_cnt;
	vid[v]=node_cnt++;
	rev[vid[v]]=v;
	for(auto u:E[v]){
		if(u.second==p)continue;
		d[u.second]=d[v]+u.first;
		dfs(u.second,v);
	}
	cr[v]=node_cnt;
}

int ty[200000],v[200000];
ll t[200000],l[200000];

struct st{
	ll v;	 //頂点のid
	P p;     //(出発時間、持続時間)
	int id;  //何番目に追加される?
	int X,Y; //bucketで使う情報
};

const int B=1000;

vector<st>vs; //全灯籠の列 (Euler Tour順序でソート)
int pos[200000];

struct Bucket{
	BIT2D bit;
	vector<ll>xs,ys;
	vector<int>idx;

	void pre_add(st&s){
		ll X=s.p.first+d[s.v],Y=d[s.v]-s.p.second;
		xs.push_back(X);
		ys.push_back(Y);
		idx.push_back(pos[s.id]);
	}
	
	void init(){
		sort(xs.begin(),xs.end());xs.erase(unique(xs.begin(),xs.end()),xs.end());
		sort(ys.begin(),ys.end());ys.erase(unique(ys.begin(),ys.end()),ys.end());
		for(int i:idx){
			vs[i].X=lower_bound(xs.begin(),xs.end(),vs[i].p.first+d[vs[i].v])-xs.begin();
			vs[i].Y=lower_bound(ys.begin(),ys.end(),d[vs[i].v]-vs[i].p.second)-ys.begin();
		}
		bit=BIT2D(xs.size(),ys.size());
	}

	void add(int id){
		bit.add(vs[id].X,vs[id].Y,1);
	}

	int query(ll x,ll y){
		x=upper_bound(xs.begin(),xs.end(),x)-xs.begin();
		y=upper_bound(ys.begin(),ys.end(),y)-ys.begin();
		return bit.sum(x-1,y-1);
	}
}bucket[100000];

int main(){
	int n,q;cin>>n>>q;
	assert(1<=n&&n<=50000);
	assert(1<=q&&q<=100000);
	rep(i,n-1){
		int a,b;ll c;scanf("%d%d%lld",&a,&b,&c);a--;b--;
		assert(0<=a&&a<n);
		assert(0<=b&&b<n);
		assert(1<=c&&c<=1e12);
		E[a].push_back(P(c,b));
		E[b].push_back(P(c,a));
	}
	dfs(0,-1);
	rep(i,q){
		scanf("%d%d%lld%lld",&ty[i],&v[i],&t[i],&l[i]);v[i]--;
		assert(0<=ty[i]&&ty[i]<=1);
		assert(ty[i]==0||l[i]==0);
		assert(0<=v[i]&&v[i]<n);
		assert(0<=t[i]&&t[i]<=1e12);
		assert(0<=l[i]&&l[i]<=1e12);
		if(ty[i]==0)vs.push_back({v[i],P(t[i],l[i]),i});
	}
	sort(vs.begin(),vs.end(),[&](st a,st b){return vid[a.v]<vid[b.v];});
	rep(i,vs.size()){
		pos[vs[i].id]=i;
	}
	for(int i=0;i<vs.size();i+=B){
		for(int j=i;j<i+B&&j<vs.size();j++){
			bucket[i/B].pre_add(vs[j]);
		}
		bucket[i/B].init();
	}
	rep(i,n){
		int ok1=vs.size(),ng1=-1;
		while(ok1-ng1>1){
			int t=(ok1+ng1)/2;
			if(vid[vs[t].v]>=cl[i])ok1=t;
			else ng1=t;
		}
		int ok2=vs.size(),ng2=-1;
		while(ok2-ng2>1){
			int t=(ok2+ng2)/2;
			if(vid[vs[t].v]>=cr[i])ok2=t;
			else ng2=t;
		}
		cl[i]=ok1;
		cr[i]=ok2;
	}
	rep(i,q){
		if(ty[i]==0){
			bucket[pos[i]/B].add(pos[i]);
		}
		else{
			int L=cl[v[i]],R=cr[v[i]];
			int ans=0;
			ll X=d[v[i]]+t[i],Y=d[v[i]];
			while(L<R&&L%B!=0){
				if(vs[L].id<=i&&vs[L].p.first+d[vs[L].v]<=X
				&&d[vs[L].v]-vs[L].p.second<=Y)ans++;
				L++;
			}
			while(L<R&&R%B!=0){
				R--;
				if(vs[R].id<=i&&vs[R].p.first+d[vs[R].v]<=X&&
				d[vs[R].v]-vs[R].p.second<=Y)ans++;
			}
			for(int i=L;i<R;i+=B){
				ans+=bucket[i/B].query(X,Y);
			}
			printf("%d\n",ans);
		}
	}
}