Submission #1367387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367387		sampaio_kk	Pairs (IOI07_pairs)	C++20	35 / 100	125 ms	25260 KiB

pairs

#include <bits/stdc++.h>
// #define int long long
#define fr first
#define sc second
#define lsb(x) (x&(-x))
#define all(x) x.begin(), x.end()
#define inv(x) x, vector<x>, greater<x>
#define pq priority_queue
#define pb push_back
using namespace std;
using pii = pair<int, int>;
using pip = pair<int, pii>;
using ppp = pair<pii, pii>;
void s1(){
        int n, d, m; cin >> n >> d >> m;
        vector<int> v(n);
        for(int i = 0; i < n; i++) cin >> v[i];
        sort(all(v));
        int l = 0, r = 0, ans = 0;
        while(r < n){
                if(v[r] - v[l] > d) l++;
                else{
                        ans += r-l;
                        r++;
                }
        }
        cout << ans << ' ';
}
struct pt{
        int x, y;
        bool operator<(pt& o){
                if(x != o.x) return x < o.x;
                return y < o.y;
        }
        void t(){
                x = x-y;
                y = x+2*y;
                y += 75000;
        }
};
void s2(){
        int n, d, m; cin >> n >> d >> m;
        vector<pt> pts(n);
        for(int i = 0; i < n; i++){
                cin >> pts[i].x >> pts[i].y;
                pts[i].t();
        }        
        sort(all(pts));
        vector<int> bit(250001);
        auto query = [&](int x){
                int ans = 0;
                while(x > 0){
                        ans += bit[x];
                        x -= (x&-x);
                }
                return ans;
        };
        auto update = [&](int x, int u){
                while(x < bit.size()){
                        bit[x] += u;
                        x += (x&-x);
                }
        };
        int ans = 0;
        int l = 0, r = 0;
        while(r < n){
                while(pts[r].x - pts[l].x > d){
                        update(pts[l].y, -1);
                        l++;
                }
                ans += query(pts[r].y + d) - query(pts[r].y-d-1);
                update(pts[r].y, 1);
                r++;
        }
        cout << ans << ' ';
}
struct ptx{
        int x, y, z, w;
        bool operator<(const ptx &o){
                if(x != o.x) return x < o.x;
                if(y != o.y) return y < o.y;
                if(z != o.z) return z < o.z;
                return w < o.w;
        }
};
struct cd{
        int x, y, z;
        ptx t(){
                return{
                        x+y+z,
                        x+y-z + 76,
                        x-y+z + 76,
                        -x+y+z + 76
                };
        }
};
static int bit[236][236][236];
void s3(){
        int n, d, m; cin >> n >> d >> m;
        vector<ptx> v(n);
        for(int i = 0; i < n; i++){
                cd x; cin >> x.x >> x.y >> x.z;
                v[i] = x.t();
        }
        sort(all(v));
        int ans = 0;
        auto query = [&](int x, int y, int z){
                x = min(235, x);
                y = min(235, y);
                z = min(235, z);
                int ans = 0;
                for(int i = x; i > 0; i -= lsb(i)){
                        for(int j = y; j > 0; j -= lsb(j)){
                                for(int k = z; k > 0; k -= lsb(k)){
                                        ans += bit[i][j][k];            
                                }
                        }
                }
                return ans;
        };
        auto query_range = [&](int y, int z, int w) {
                int y1 = y-d-1, y2 = y+d;
                int z1 = z-d-1, z2 = z+d;
                int w1 = w-d-1, w2 = w+d;
                
                return query(y2, z2, w2)
                     - query(y1, z2, w2) - query(y2, z1, w2) - query(y2, z2, w1)
                     + query(y1, z1, w2) + query(y1, z2, w1) + query(y2, z1, w1)
                     - query(y1, z1, w1);
            };
        auto update = [&](int x, int y, int z, int u){
                for(int i = x; i < 235; i += lsb(i)){
                        for(int j = y; j < 235; j += lsb(j)){
                                for(int k = z; k < 235; k += lsb(k)){
                                        bit[i][j][k] += u; 
                                }
                        }
                }
        };
        int l = 0;
        for(int r = 0; r < n; r++){
                while(v[r].x - v[l].x > d){
                        auto[x, y, z, w] = v[l];
                        update(y, z, w, -1);
                        l++;
                }
                auto [x, y, z, w] = v[r];
                ans += query_range(y, z, w);
                update(y, z, w, 1);
        }
        cout << ans << '\n';
}
signed main(){
        int b; cin >> b;
        if(b == 1) s1();
        if(b == 2) s2();
        if(b == 3) s3();
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 10 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10