Submission #410453

#	Time	Username	Problem	Language	Result	Execution time	Memory
410453		jeroenodb	Pairs (IOI07_pairs)	C++14	100 / 100	128 ms	3976 KiB

pairs

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 2e5+1, oo = 1e9;

int n,d;
void solve1() {
    vi a(n); for(auto& i: a) cin >> i;
    sort(all(a));
    ll ans =0;
    for(int i=0,j=0;i<n;++i) {
        while(a[i]-a[j]>d) 
            ++j;
        ans+=i-j;
    }
    cout << ans << '\n';
}

namespace fen {
    int fenwick[mxN]={};
    int prefixsum(int i) {
        int ans = 0;
        while(i) {
            ans+=fenwick[i];
            i&=i-1;
        }
        return ans;
    }
    void increment(int i, int val) {
        while(i<=mxN) {
            fenwick[i]+=val;
            i+=i&-i;
        }
    }
    int query(int y) {
        int l = max(2,y-d),r = min(mxN-1,y+d);
        return prefixsum(r)-prefixsum(l-1);
    }
}
typedef complex<int> pt;
#define X real()
#define Y imag()
pt tr(pt p) {return pt{p.X+p.Y,p.Y-p.X}; } // 45 degree rotate
bool comp(const pt& a, const pt& b) { return a.X<b.X or (a.X==b.X and a.Y < b.Y);}
void read(pt& p) {
    int a,b; cin >> a >> b;
    p = {a,b};
}
struct event {
    int x,y;
    bool add=true;
    bool operator<(const event& o) const {
        if(x!=o.x)
            return x<o.x;
        return add>o.add;
    }
};
void solve2() {
    // 2d points
    vector<pt> vp(n);
    vector<event> es; es.reserve(2*n);
    for(auto& p: vp) {
        read(p);
        p=tr(p);
        es.push_back({p.X,p.Y+mxN/2,true});
        es.push_back({p.X+d,p.Y+mxN/2,false});
    }
    sort(all(es));
    ll ans = 0;
    for(auto& e: es) {
        if(e.add) {
            ans+=fen::query(e.y);
            fen::increment(e.y,1);
        } else {
            fen::increment(e.y,-1);
        }
    }
    cout << ans << '\n';
}

struct prefsum {
    static const int k=76;
    int pref[2*k][2*k];
    void reset() {
        for(int i=0;i<2*k;++i) {
            fill(pref[i],pref[i]+2*k,0);
        }
    }
    void add(pt p) {
        p = tr(p);
        int x=p.X,y=p.Y+k-1;
        pref[x][y]++;
    }
    void build() {
        for(int i=1;i<2*k;++i) for(int j=1;j<2*k;++j) {
            pref[i][j]+=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
        }
    }
    int query(pt p, int dd) {
        p = tr(p);
        int x=p.X,y=p.Y+k-1;
        int rx=min(2*k-1,x+dd),ry=min(2*k-1,y+dd);
        int lx = max(1,x-dd),ly = max(1,y-dd);
        return pref[rx][ry]-pref[rx][ly-1]-pref[lx-1][ry]+pref[lx-1][ly-1];        
    }
};
void solve3() {
    vector<pt> vp[76];
    for(int i=0;i<n;++i) {
        int x,y,z; cin >> x >> y >> z;
        vp[z].push_back({x,y});
    }
    prefsum pf;
    ll ans = 0;
    for(int i=1;i<=75;++i) {
        if(vp[i].empty()) continue;
        pf.reset();
        for(auto& p:vp[i]) {
            pf.add(p);
        }
        pf.build();
        for(int j=1;j<=75;++j) {
            int dist = abs(i-j);
            if(dist>d) continue;
            for(auto& p: vp[j]) {
                ans+=pf.query(p,d-dist);
            }
        }
    }
    cout << (ans-n)/2 << '\n';

}
int main() {
    int b,m;cin >> b >> n >> d >> m;
    if(b==1) solve1();
    else if(b==2) solve2();
    else solve3();

}

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