oj.uz

Submission #410453

# Submission time Handle Problem Language Result Execution time Memory
410453 2021-05-22T17:24:43 Z jeroenodb Pairs (IOI07_pairs) C++14
100 / 100
 128 ms 3976 KB 
#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.0 / 6.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 680 KB Output is correct
2 Correct 32 ms 588 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 588 KB Output is correct
2 Correct 47 ms 588 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 680 KB Output is correct
2 Correct 49 ms 588 KB Output is correct
3 Correct 48 ms 680 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 3 ms 844 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3420 KB Output is correct
2 Correct 64 ms 3440 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3424 KB Output is correct
2 Correct 76 ms 3456 KB Output is correct
3 Correct 76 ms 3488 KB Output is correct
4 Correct 78 ms 3344 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 3960 KB Output is correct
2 Correct 106 ms 3880 KB Output is correct
3 Correct 107 ms 3908 KB Output is correct
4 Correct 89 ms 3976 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 412 KB Output is correct
2 Correct 8 ms 332 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1592 KB Output is correct
2 Correct 62 ms 2252 KB Output is correct
3 Correct 69 ms 2212 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 1644 KB Output is correct
2 Correct 109 ms 2360 KB Output is correct
3 Correct 103 ms 2360 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1504 KB Output is correct
2 Correct 119 ms 2372 KB Output is correct
3 Correct 128 ms 2336 KB Output is correct