제출 #120710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120710		baluteshih	Pairs (IOI07_pairs)	C++14	100 / 100	3842 ms	11132 KiB

pairs

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct mode
{
	ll x,y,z;
}arr2[100005];

ll ans=0,bit[2][200005],cnt[80][80][80],pre[80][80][80],all[2],d;
pll arr[100005];
vector<ll> v;

void modify(ll t,ll x,ll val)
{
	for(all[t]+=val;x<=v.size();x+=x&-x) bit[t][x]+=val;
}

ll query(ll t,ll x)
{
	ll re=0;
	for(;x;x-=x&-x) re+=bit[t][x];
	return re;
}

void DQ(ll l,ll r)
{
	if(l==r) return;
	ll mid=l+r>>1,a,b;
	DQ(l,mid),DQ(mid+1,r);
	queue<pll> q;
	for(a=l;a<=mid;++a)
		modify(0,upper_bound(ALL(v),arr[a].F-arr[a].S)-v.begin(),1);
	for(a=l,b=mid+1;a<=mid&&b<=r;)
		if(arr[a].S<=arr[b].S)
			modify(0,upper_bound(ALL(v),arr[a].F-arr[a].S)-v.begin(),-1),modify(1,upper_bound(ALL(v),arr[a].F+arr[a].S)-v.begin(),1),q.push(arr[a++]);
		else
			ans+=all[0]-query(0,lower_bound(ALL(v),arr[b].F-arr[b].S-d)-v.begin())+all[1]-query(1,lower_bound(ALL(v),arr[b].F+arr[b].S-d)-v.begin()),q.push(arr[b++]);
	while(a<=mid)
		modify(0,upper_bound(ALL(v),arr[a].F-arr[a].S)-v.begin(),-1),modify(1,upper_bound(ALL(v),arr[a].F+arr[a].S)-v.begin(),1),q.push(arr[a++]);
	while(b<=r)
		ans+=all[1]-query(1,lower_bound(ALL(v),arr[b].F+arr[b].S-d)-v.begin()),q.push(arr[b++]);
	for(a=l;a<=mid;++a)
		modify(1,upper_bound(ALL(v),arr[a].F+arr[a].S)-v.begin(),-1);
	for(int i=l;i<=r;++i)
		arr[i]=q.front(),q.pop();
}
 
int main()
{jizz
	ll b,n,m,x;
	cin >> b >> n >> d >> m;
	if(b==1)
	{
		for(int i=0;i<n;++i)
			cin >> x,v.pb(x);
		sort(ALL(v));
		for(int i=1;i<v.size();++i)
			ans+=v.begin()+i-lower_bound(ALL(v),v[i]-d);
		cout << ans << "\n";
	}
	else if(b==2)
	{
		for(int i=0;i<n;++i)
			cin >> arr[i].F >> arr[i].S,v.pb(arr[i].F+arr[i].S),v.pb(arr[i].F-arr[i].S);
		sort(arr,arr+n),sort(ALL(v)),v.resize(unique(ALL(v))-v.begin());
		DQ(0,n-1);
		cout << ans << "\n";
	}
	else
	{
		for(int i=0;i<n;++i)
			cin >> arr2[i].x >> arr2[i].y >> arr2[i].z,++cnt[arr2[i].x][arr2[i].y][arr2[i].z];
		for(int i=1;i<=m;++i)
		{
			for(int j=1;j<=m;++j)
				for(int k=1;k<=m;++k)
					pre[i][j][k]=pre[i][j][k-1]+cnt[i][j][k];
		}
		for(int i=0;i<n;++i)
		{
			for(int j=1;j<=m;++j)
				if(d>=abs(arr2[i].x-j))
				{
					int nd=d-abs(arr2[i].x-j);
					for(int k=1;k<=m;++k)
						if(nd>=abs(arr2[i].y-k))
							ans+=pre[j][k][min(m,arr2[i].z+nd-abs(arr2[i].y-k))]-pre[j][k][max(1LL,arr2[i].z-nd+abs(arr2[i].y-k))-1];
				}
			--ans;
		}
		cout << ans/2 << "\n";
	}
}

컴파일 시 표준 에러 (stderr) 메시지

pairs.cpp: In function 'void modify(ll, ll, ll)':
pairs.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(all[t]+=val;x<=v.size();x+=x&-x) bit[t][x]+=val;
                  ~^~~~~~~~~~
pairs.cpp: In function 'void DQ(ll, ll)':
pairs.cpp:40:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll mid=l+r>>1,a,b;
         ~^~
pairs.cpp: In function 'int main()':
pairs.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<v.size();++i)
               ~^~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10