oj.uz

Submission #120721

# Submission time Handle Problem Language Result Execution time Memory
120721 2019-06-25T10:19:24 Z baluteshih Pairs (IOI07_pairs) C++14
100 / 100
 660 ms 53404 KB 
#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][230][230],pre[80][230][230],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,M=0;
	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+m+1][arr2[i].y-arr2[i].z+m+1],M=max(M,arr2[i].y+arr2[i].z+m+1);
		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]=cnt[i][j][k]-pre[i][j-1][k-1]+pre[i][j-1][k]+pre[i][j][k-1];
		for(int i=0;i<n;++i)
		{
			ll y=arr2[i].y+arr2[i].z+m+1,z=arr2[i].y-arr2[i].z+m+1;
			for(int j=1;j<=m;++j)
				if(d>=abs(arr2[i].x-j))
				{
					ll nd=d-abs(arr2[i].x-j);
					ll x1=min(M,y+nd),y1=min(M,z+nd),x2=max(1LL,y-nd)-1,y2=max(1LL,z-nd)-1;
					ans+=pre[j][x1][y1]-pre[j][x1][y2]-pre[j][x2][y1]+pre[j][x2][y2];
				}
			--ans;
		}
		cout << ans/2 << "\n";
	}
}

Compilation message

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1532 KB Output is correct
2 Correct 17 ms 1532 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1532 KB Output is correct
2 Correct 22 ms 1532 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1532 KB Output is correct
2 Correct 23 ms 1532 KB Output is correct
3 Correct 22 ms 1532 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 5196 KB Output is correct
2 Correct 159 ms 5160 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 5156 KB Output is correct
2 Correct 356 ms 5256 KB Output is correct
3 Correct 310 ms 5224 KB Output is correct
4 Correct 323 ms 5352 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 6648 KB Output is correct
2 Correct 660 ms 6560 KB Output is correct
3 Correct 331 ms 5480 KB Output is correct
4 Correct 331 ms 5224 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 34424 KB Output is correct
2 Correct 41 ms 34424 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3704 KB Output is correct
2 Correct 27 ms 3704 KB Output is correct
3 Correct 26 ms 3832 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 35320 KB Output is correct
2 Correct 268 ms 35192 KB Output is correct
3 Correct 115 ms 35320 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 53404 KB Output is correct
2 Correct 449 ms 53376 KB Output is correct
3 Correct 255 ms 53380 KB Output is correct