oj.uz

Submission #120710

# Submission time Handle Problem Language Result Execution time Memory
120710 2019-06-25T09:51:05 Z baluteshih Pairs (IOI07_pairs) C++14
100 / 100
 3842 ms 11132 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][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";
	}
}

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 18 ms 1916 KB Output is correct
2 Correct 18 ms 1916 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2320 KB Output is correct
2 Correct 23 ms 2300 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2272 KB Output is correct
2 Correct 25 ms 2300 KB Output is correct
3 Correct 23 ms 2300 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 5736 KB Output is correct
2 Correct 160 ms 5876 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 5988 KB Output is correct
2 Correct 362 ms 5992 KB Output is correct
3 Correct 312 ms 5992 KB Output is correct
4 Correct 325 ms 5988 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 7708 KB Output is correct
2 Correct 647 ms 7656 KB Output is correct
3 Correct 339 ms 6376 KB Output is correct
4 Correct 336 ms 6440 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6656 KB Output is correct
2 Correct 50 ms 6656 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3456 KB Output is correct
2 Correct 50 ms 3576 KB Output is correct
3 Correct 48 ms 3520 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 8440 KB Output is correct
2 Correct 1799 ms 8412 KB Output is correct
3 Correct 2344 ms 8508 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1212 ms 11128 KB Output is correct
2 Correct 3014 ms 11132 KB Output is correct
3 Correct 3842 ms 11132 KB Output is correct