oj.uz

Submission #120635

# Submission time Handle Problem Language Result Execution time Memory
120635 2019-06-25T06:32:52 Z baluteshih Pairs (IOI07_pairs) C++14
70 / 100
 4000 ms 7784 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],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;
		for(int i=0;i<n;++i)
			for(int j=i+1;j<n;++j)
				if(abs(arr2[i].x-arr2[j].x)+abs(arr2[i].y-arr2[j].y)+abs(arr2[i].z-arr2[j].z)<=d)
					++ans;
		cout << ans << "\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 3 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 17 ms 1916 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2332 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 26 ms 2300 KB Output is correct
2 Correct 25 ms 2300 KB Output is correct
3 Correct 25 ms 2300 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 404 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 168 ms 5712 KB Output is correct
2 Correct 163 ms 5676 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 5992 KB Output is correct
2 Correct 361 ms 6204 KB Output is correct
3 Correct 307 ms 5992 KB Output is correct
4 Correct 322 ms 5992 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 7728 KB Output is correct
2 Correct 674 ms 7784 KB Output is correct
3 Correct 330 ms 6388 KB Output is correct
4 Correct 327 ms 6380 KB Output is correct

Subtask #10
10.0 / 10.0

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

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4078 ms 3320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4005 ms 3584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4018 ms 3576 KB Time limit exceeded
2 Halted 0 ms 0 KB -