oj.uz

답안 #697347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697347 2023-02-09T11:30:52 Z WongChun1234 Pairs (IOI07_pairs) C++14
100 / 100
 3638 ms 9560 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
const bool DEBUG=0;
ll b,n,d,m,x[N],y[N],z[N],ans;
ll pt=1,psum[150][150][150],par,dy;
vector<pair<int,int>> srt;
void sub1(){
    for (int i=1;i<=n;i++){
        cin>>x[i];
    }
    sort(x+1,x+1+n);
    for (int i=1;i<=n;i++){
        while (x[pt]<x[i]-d) pt++;
        ans+=i-pt;
    }
    cout<<ans<<"\n";
}
const int D=115000;
struct bit{
	const static int size=300060;
	array<int,size> bit;
	void modify(int id,int val){
		for (;id<size;id+=(id&-id)) bit[id]+=val;
	}
	int query(int id){
		int ret=0;
		for (;id;id-=(id&-id)) ret+=bit[id];
		return ret;
	}
	int query(int l,int r){
	    if (DEBUG) cout<<l-D<<" "<<r-D<<endl;
	    return query(r)-query(l-1);
	}
}cnt[2];
void sub2(){
    for (int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        srt.emplace_back(x[i],y[i]);
    }
    sort(srt.begin(),srt.end(),[](pair<int,int> a, pair<int,int> b) {return a.first+a.second < b.first+b.second;});
    auto curr=srt.begin();
    for (auto i:srt){
        while ((*curr).first+(*curr).second<i.first+i.second-d){
            par=((*curr).first+(*curr).second)%2;
            cnt[par].modify(((*curr).second-(*curr).first+par)/2+D,-1),curr++;
        }
        if (DEBUG) cout<<i.first<<" "<<i.second<<endl;
        par=(i.first+i.second)%2;
        dy=(i.second-i.first+par)/2;
        if (d%2){
            if (par){
                ans+=cnt[!par].query(dy-d/2-1+D,dy+d/2+D);
                ans+=cnt[par].query(dy-d/2+D,dy+d/2+D);
            }else{
                ans+=cnt[!par].query(dy-d/2+D,dy+d/2+1+D);
                ans+=cnt[par].query(dy-d/2+D,dy+d/2+D);
            }
        }else{
            if (par){
                ans+=cnt[par].query(dy-d/2+D,dy+d/2+D);
                ans+=cnt[!par].query(dy-d/2+D,dy+d/2-1+D);
            }else{
                ans+=cnt[par].query(dy-d/2+D,dy+d/2+D);
                ans+=cnt[!par].query(dy-d/2+1+D,dy+d/2+D);
            }
        }
        cnt[par].modify((i.second-i.first+par)/2+D,1);
        if (DEBUG) cout<<ans<<"\n";
    }
    cout<<ans<<"\n";
}
void sub3(){
    for (int i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>z[i];
        psum[x[i]][y[i]][z[i]]++;
    }
    for (int i=1;i<=75;i++) for (int j=1;j<=75;j++) for (int k=1;k<=75;k++) psum[i][j][k]+=psum[i][j][k-1];
    for (int i=1;i<=n;i++){
        for (int xx=max(1LL,x[i]-d);xx<=min(m,x[i]+d);xx++){
            int dx=abs(x[i]-xx);
            for (int yy=max(1LL,y[i]-(d-dx));yy<=min(m,y[i]+(d-dx));yy++){
                int maxdz=d-dx-abs(y[i]-yy);
                ans+=psum[xx][yy][min(m,z[i]+maxdz)]-psum[xx][yy][max(0LL,z[i]-maxdz-1)];
            }
        }
    }
    cout<<(ans-n)/2<<"\n";
}
int main(){
    cin>>b>>n>>d>>m;
    if (b==1) sub1();
    else if (b==2) sub2();
    else if (b==3) sub3();
    else assert(0);
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 980 KB Output is correct
2 Correct 23 ms 1108 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 1004 KB Output is correct
2 Correct 40 ms 1072 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 976 KB Output is correct
2 Correct 54 ms 1096 KB Output is correct
3 Correct 53 ms 1080 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 2824 KB Output is correct
2 Correct 46 ms 2940 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 2752 KB Output is correct
2 Correct 59 ms 3560 KB Output is correct
3 Correct 57 ms 3548 KB Output is correct
4 Correct 52 ms 3544 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 3388 KB Output is correct
2 Correct 68 ms 3516 KB Output is correct
3 Correct 68 ms 4408 KB Output is correct
4 Correct 72 ms 4416 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7124 KB Output is correct
2 Correct 45 ms 7244 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 9488 KB Output is correct
2 Correct 90 ms 9516 KB Output is correct
3 Correct 85 ms 9392 KB Output is correct

Subtask #12
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 9512 KB Output is correct
2 Correct 1219 ms 9560 KB Output is correct
3 Correct 1428 ms 9512 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 761 ms 9548 KB Output is correct
2 Correct 3163 ms 9512 KB Output is correct
3 Correct 3638 ms 9516 KB Output is correct