Submission #1313159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313159		viyeuquadamdau	Pairs (IOI07_pairs)	C++20	60 / 100	588 ms	387340 KiB

pairs

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define vec vector
#define PB push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define ull unsigned long long
#define pii pair<int,int>
#define rz resize
#define ld long double
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define matrix vec<vec<int>>
#define MP make_pair

const int N = 1e5+5;
const ll INF = 1e18;
const ll mod = 998244353;

mt19937_64 rng(time(0));
int random(int a, int b){ return uniform_int_distribution<ll>(a,b)(rng); }

int add(int a, int b) { a+=b;if(a>=mod)a-=mod; return a; }

struct Fen
{
    vec<int>f;
    int n;
    void assign(int _n){
        n=_n;f.rz(n+1);
    }
    void upd(int x, int v){ for(;x<=n;x+=x&-x)f[x]+=v; }
    void upd(int l, int r, int x){ upd(l,x);upd(r+1,-x); } 
    int quer(int x){ int r=0;for(;x>0;x-=x&-x)r+=f[x];return r; }
};

int B,n,d,M;

namespace D2 {
    void solve() {
        vec<pii>a(n+1);
        vec<int>st(n+1);
        vec<int>vals;
        for(int i=1;i<=n;++i)
            cin>>a[i].F>>a[i].S,vals.PB(a[i].F-a[i].S),
        vals.PB(a[i].F-a[i].S-d),vals.PB(a[i].F-a[i].S+d),st[i]=a[i].F+a[i].S;
        sort(a.begin()+1,a.end(),[&](const pii& fi, const pii& se){
            return (fi.F+fi.S == se.F+se.S ? fi.F-fi.S < se.F-se.S : fi.F+fi.S < se.F+se.S);
        });
        sort(all(vals));
        sort(st.begin()+1,st.end());
        auto getid=[&](int x)->int{
            return lower_bound(all(vals),x)-vals.begin()+1;
        };
        Fen f;f.assign(3*n+2);
        int an=0;
        for(int i=1,j=1;i<=n;++i){
            while(j < i && st[i]-st[j] > d){
                int u=a[j].F-a[j].S;
                int cl=getid(u-d),cr=getid(u+d);
                f.upd(cl,cr,-1);++j;
            }
            int v=a[i].F-a[i].S;
            int cl=getid(v-d),cr=getid(v+d);
            an+=f.quer(getid(v));
            f.upd(cl,cr,1);
        }
        cout<<an;
    }
}

struct Fen3D
{
    vec<vec<vec<int>>> f;
    int x,y,z;
    Fen3D(int _x,int _y, int _z):x(_x),y(_y),z(_z){
        f.rz(x+1,vec<vec<int>>(y+1,vec<int>(z+1)));
    }
    void upd(int a, int b, int c, int v){
        for(;a<=x;a+=a&-a)for(int i=b;i<=y;i+=i&-i)for(int j=c;j<=z;j+=j&-j)f[a][i][j]+=v;
    }
    void upd(int a1, int a2, int b1, int b2, int c1, int c2, int v){

        auto add=[&](int a, int b, int c, int v)->void{
            if(a<=0 || b <= 0 || c <= 0)return;
            if(a>x || b>y || c>z)return ;
            upd(a,b,c,v);
        };
        add(a1,b1,c1,v);
        add(a1,b1,c2+1,-v);
        add(a1,b2+1,c1,-v);
        add(a1,b2+1,c2+1,v);
        add(a2+1,b1,c1,-v);
        add(a2+1,b1,c2+1,v);
        add(a2+1,b2+1,c1,v);
        add(a2+1,b2+1,c2+1,-v);
    }
    int quer(int a, int b, int c){
        int r=0;
        for(;a>0;a-=a&-a)for(int i=b;i>0;i-=i&-i)for(int j=c;j>0;j-=j&-j)r+=f[a][i][j];
        return r;
    }

};


namespace D3 {
    void solve(){
        vec<array<int,3>>ar(n+1);
        vec<int> vals;

        for(int i=1;i<=n;++i){
            for(int j=0;j<B;++j)cin>>ar[i][j];
            vec<int> add={
                ar[i][0]+ar[i][1]-ar[i][2],
                ar[i][0]-ar[i][1]-ar[i][2],
                ar[i][0]-ar[i][1]+ar[i][2]
            };
            for(int j=0;j<3;++j)vals.PB(add[j]),vals.PB(add[j]-d),vals.PB(add[j]+d);
        }
        sort(ar.begin()+1,ar.end(),[&](array<int,3>& fi, array<int,3>& se){
            return fi[0]+fi[1]+fi[2] < se[0]+se[1]+se[2];
        });
        sort(all(vals));vals.rz(unique(all(vals))-vals.begin());
        auto getid=[&](int x)->int{
            return lower_bound(all(vals),x)-vals.begin()+1;
        };
        int len=vals.size();
        Fen3D f(len+5,len+5,len+5);
        int an=0;
        for(int i=1,j=1;i<=n;++i){
            while(j < i){
                int u1=ar[i][0]+ar[i][1]+ar[i][2];
                int u2=ar[j][0]+ar[j][1]+ar[j][2];
                if(u1-u2 > d){
                    int a1=getid(ar[i][0]+ar[i][1]-ar[i][2]-d);
                    int a2=getid(ar[i][0]+ar[i][1]-ar[i][2]+d);
                    int b1=getid(ar[i][0]-ar[i][1]-ar[i][2]-d);
                    int b2=getid(ar[i][0]-ar[i][1]-ar[i][2]+d);
                    int c1=getid(ar[i][0]-ar[i][1]+ar[i][2]-d);
                    int c2=getid(ar[i][0]-ar[i][1]+ar[i][2]+d);
                    f.upd(a1,a2,b1,b2,c1,c2,-1);
                    ++j;}
                else break;
            }
            int a=getid(ar[i][0]+ar[i][1]-ar[i][2]);
            int b=getid(ar[i][0]-ar[i][1]-ar[i][2]);
            int c=getid(ar[i][0]-ar[i][1]+ar[i][2]);
            an += f.quer(a,b,c);
            int a1=getid(ar[i][0]+ar[i][1]-ar[i][2]-d);
            int a2=getid(ar[i][0]+ar[i][1]-ar[i][2]+d);
            int b1=getid(ar[i][0]-ar[i][1]-ar[i][2]-d);
            int b2=getid(ar[i][0]-ar[i][1]-ar[i][2]+d);
            int c1=getid(ar[i][0]-ar[i][1]+ar[i][2]-d);
            int c2=getid(ar[i][0]-ar[i][1]+ar[i][2]+d);
            f.upd(a1,a2,b1,b2,c1,c2,1);
        }
        cout<<an;

    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("NgheLen.Inp","r",stdin);
    // freopen("NgheLen.out","w",stdout);
    cin>>B;
    cin>>n;
    cin>>d;
    cin>>M;
    if(B==1){
        vec<int>a(n+1);
        for(int i=1;i<=n;++i)cin>>a[i];
        sort(a.begin()+1,a.end());
        int j=1,an=0;
        for(int i=1;i<=n;++i){
            while(a[i]-a[j] > d)++j;
            an += (i-j);
        }
        cout<<an<<'\n';
    } else if(B==2){
        D2::solve();
    } else {
        D3::solve();
    }


    return 0;
}

• 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: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10