提出 #34878769

---

ソースコード 拡げる

#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<cassert>
using namespace std;
struct segtree1D{
	vector<int>idx;
	vector<long>dat;
	segtree1D(vector<int>fidx)
	{
		sort(fidx.begin(),fidx.end());
		fidx.erase(unique(fidx.begin(),fidx.end()),fidx.end());
		idx.swap(fidx);
		dat.assign(idx.size(),(long)-1e18);
	}
	void set(int id,long x)
	{
		int i=lower_bound(idx.begin(),idx.end(),id)-idx.begin();
		assert(i<idx.size()&&idx[i]==id);
		i++;
		for(;i<=dat.size();i+=i&-i)dat[i-1]=max(dat[i-1],x);
	}
	long prod(int r)
	{
		r=lower_bound(idx.begin(),idx.end(),r)-idx.begin();
		long ret=(long)-1e18;
		for(;r;r-=r&-r)ret=max(ret,dat[r-1]);
		return ret;
	}
};
struct segtree2D{
	vector<int>idx;
	vector<vector<int> >idx1D;
	vector<segtree1D>dat;
	segtree2D(vector<pair<int,int> >fidx)
	{
		sort(fidx.begin(),fidx.end());
		for(int i=0;i<fidx.size();)
		{
			int x=fidx[i].first;
			idx.push_back(x);
			idx1D.emplace_back();
			while(i<fidx.size()&&fidx[i].first==x)i++;
		}
		int R=0;
		for(int i=0;i<fidx.size();)
		{
			int x=fidx[i].first;
			R++;
			while(i<fidx.size()&&fidx[i].first==x)
			{
				int y=fidx[i++].second;
				int r=R;
				for(;r<=idx1D.size();r+=r&-r)idx1D[r-1].emplace_back(y);
			}
			dat.emplace_back(segtree1D(idx1D[R-1]));
		}
	}
	void set(pair<int,int>id,long x)
	{
		int i=lower_bound(idx.begin(),idx.end(),id.first)-idx.begin();
		assert(i<idx.size()&&idx[i]==id.first);
		i++;
		for(;i<=dat.size();i+=i&-i)dat[i-1].set(id.second,x);
	}
	long prod(pair<int,int>r)
	{
		int ri=lower_bound(idx.begin(),idx.end(),r.first)-idx.begin();
		long ret=(long)-1e18;
		for(;ri;ri-=ri&-ri)ret=max(ret,dat[ri-1].prod(r.second));
		return ret;
	}
};
struct segtree3D{
	vector<int>idx;
	vector<vector<pair<int,int> > >idx2D;
	vector<segtree2D>dat;
	segtree3D(vector<pair<int,pair<int,int> > >fidx)
	{
		sort(fidx.begin(),fidx.end());
		for(int i=0;i<fidx.size();)
		{
			int x=fidx[i].first;
			idx.push_back(x);
			idx2D.emplace_back();
			while(i<fidx.size()&&fidx[i].first==x)i++;
		}
		int R=0;
		for(int i=0;i<fidx.size();)
		{
			int x=fidx[i].first;
			R++;
			while(i<fidx.size()&&fidx[i].first==x)
			{
				pair<int,int>y=fidx[i++].second;
				int r=R;
				for(;r<=idx2D.size();r+=r&-r)idx2D[r-1].emplace_back(y);
			}
			dat.emplace_back(segtree2D(idx2D[R-1]));
		}
	}
	void set(pair<int,pair<int,int> >id,long x)
	{
		int i=lower_bound(idx.begin(),idx.end(),id.first)-idx.begin();
		assert(i<idx.size()&&idx[i]==id.first);
		i++;
		for(;i<=dat.size();i+=i&-i)dat[i-1].set(id.second,x);
	}
	long prod(pair<int,pair<int,int> >r)
	{
		int ri=lower_bound(idx.begin(),idx.end(),r.first)-idx.begin();
		long ret=(long)-1e18;
		for(;ri;ri-=ri&-ri)ret=max(ret,dat[ri-1].prod(r.second));
		return ret;
	}
};
int N;
tuple<int,int,int,int>TXYA[1<<17];
main()
{
	cin>>N;
	vector<pair<int,pair<int,int> > >Set1(N),Set2(N);
	for(int i=0;i<N;i++)
	{
		int t,x,y,a;cin>>t>>x>>y>>a;
		TXYA[i]=make_tuple(t,x,y,a);
		Set1[i]=make_pair(x,make_pair(y,t-y-x));
		Set2[i]=make_pair(-x,make_pair(y,t-y+x));
	}
	sort(TXYA,TXYA+N,[](const tuple<int,int,int,int>&l,const tuple<int,int,int,int>&r){return get<0>(l)<get<0>(r);});
	sort(Set1.begin(),Set1.end());
	Set1.erase(unique(Set1.begin(),Set1.end()),Set1.end());
	sort(Set2.begin(),Set2.end());
	Set2.erase(unique(Set2.begin(),Set2.end()),Set2.end());
	segtree3D seg1(Set1);
	segtree3D seg2(Set2);
	long ans=0;
	for(int i=0;i<N;i++)
	{
		long now=-1e18;
		auto[t,x,y,a]=TXYA[i];
		if(x+y<=t)now=0;
		now=max(now,seg1.prod(make_pair(x+1,make_pair(y+1,t-y-x+1))));
		now=max(now,seg2.prod(make_pair(-x+1,make_pair(y+1,t-y+x+1))));
		now+=a;
		seg1.set(make_pair(x,make_pair(y,t-y-x)),now);
		seg2.set(make_pair(-x,make_pair(y,t-y+x)),now);
		ans=max(ans,now);
	}
	cout<<ans<<endl;
}

提出情報

コンパイルエラー

In file included from /usr/include/c++/9/cassert:44,
                 from ./Main.cpp:5:
./Main.cpp: In member function ‘void segtree1D::set(int, long int)’:
./Main.cpp:20:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   20 |   assert(i<idx.size()&&idx[i]==id);
      |          ~^~~~~~~~~~~
./Main.cpp:22:9: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   22 |   for(;i<=dat.size();i+=i&-i)dat[i-1]=max(dat[i-1],x);
      |        ~^~~~~~~~~~~~
./Main.cpp: In constructor ‘segtree2D::segtree2D(std::vector<std::pair<int, int> >)’:
./Main.cpp:39:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   39 |   for(int i=0;i<fidx.size();)
      |               ~^~~~~~~~~~~~
./Main.cpp:44:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   44 |    while(i<fidx.size()&&fidx[i].first==x)i++;
      |          ~^~~~~~~~~~~~
./Main.cpp:47:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   47 |   for(int i=0;i<fidx.size();)
      |               ~^~~~~~~~~~~~
./Main.cpp:51:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   51 |    while(i<fidx.size()&&fidx[i].first==x)
      |          ~^~~~~~~~~~~~
./Main.cpp:55:11: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int> >::size_type’ {aka ‘lo...

ジャッジ結果