Submission #1263000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263000		papaulo	Pairs (IOI07_pairs)	C++20	100 / 100	144 ms	51640 KiB

pairs

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

int b, n, d, m;

struct Event1D {
    int x, exiting;
    Event1D(int x, int e) : x(x), exiting(e) {}
    bool operator<(const Event1D &e) {
        if(x!=e.x) return x>e.x;
        return exiting<e.exiting;
    }
};

struct Event2D {
    int x, y, exiting;
    Event2D(int x, int y, int e) : x(x), y(y), exiting(e) {}
    bool operator<(const Event2D &e) {
        if(x!=e.x) return x>e.x;
        return exiting<e.exiting;
    }
};

struct Event3D {
    int x, y, z, w, exiting;
    Event3D(int x, int y, int z, int w, int e) : x(x), y(y), z(z), w(w), exiting(e) {}
    bool operator<(const Event3D &e) {
        if(x!=e.x) return x>e.x;
        return exiting<e.exiting;
    }
};
#define MAXM2 200200
int bit2[MAXM2];

void update2(int i, int v) {
    for(;i<=m;i+=(i&(-i))) bit2[i]+=v;
}

int query2(int i) {
    i=min(i, m);
    int ans=0;
    for(;i>0;i-=(i&(-i))) ans+=bit2[i];
    return ans;
}

int query2(int l, int r) {
    return query2(r)-query2(l-1);
}

#define MAXM3 226
int bit3[MAXM3][MAXM3][MAXM3];

void update3(int x, int y, int z, int v) {
    for(int xx=x;xx<=m;xx+=(xx&(-xx))) {
        for(int yy=y;yy<=m;yy+=(yy&(-yy))) {
            for(int zz=z;zz<=m;zz+=(zz&(-zz))) {
                bit3[xx][yy][zz]+=v;
            }
        }
    }
}

int query3(int x, int y, int z) {
    x=min(x, m);
    y=min(y, m);
    z=min(z, m);
    int ans=0;
    for(int xx=x;xx>0;xx-=(xx&(-xx))) {
        for(int yy=y;yy>0;yy-=(yy&(-yy))) {
            for(int zz=z;zz>0;zz-=(zz&(-zz))) {
                ans+=bit3[xx][yy][zz];
            }
        }
    }
    return ans;
}

int query3(int x1, int y1, int z1, int x2, int y2, int z2) {
    --x1, --y1, --z1;
    return query3(x2, y2, z2)-query3(x2, y2, z1)-query3(x2, y1, z2)-query3(x1, y2, z2)+query3(x1, y1, z2)+query3(x1, y2, z1)+query3(x2, y1, z1)-query3(x1, y1, z1);
}

int main() {
    auto start=chrono::high_resolution_clock::now();
    memset(bit2, 0, sizeof(bit2));
    memset(bit3, 0, sizeof(bit3));
    auto end=chrono::high_resolution_clock::now();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    auto dur=chrono::duration<double>(end-start).count();
    cin >> b >> n >> d >> m;
    int64_t ans=0;
    if(b==1) {
        vector<Event1D> events;
        for(int i=0;i<n;i++) {
            int x;
            cin >> x;
            events.push_back(Event1D(x, 0));
            events.push_back(Event1D(x-d, 1));
        }
        sort(events.begin(), events.end());
        int cur=0;
        for(auto e : events) {
            if(e.exiting) {
                --cur;
            } else {
                ans+=cur;
                ++cur;
            }
        }
    } else if(b==2) {
        vector<Event2D> events;
        for(int i=0;i<n;i++) {
            int x, y;
            cin >> x >> y;
            int s=x+y;
            int t=x-y+m;
            events.push_back(Event2D(s, t, 0));
            events.push_back(Event2D(s-d, t, 1));
        }
        m*=2;
        sort(events.begin(), events.end());
        for(auto e : events) {
            if(e.exiting) {
                update2(e.y, -1);
            } else {
                ans+=query2(e.y-d, e.y+d);
                update2(e.y, 1);
            }
        }
    } else {
        vector<Event3D> events;
        for(int i=0;i<n;i++) {
            int x, y, z;
            cin >> x >> y >> z;
            int s=x+y+z;
            int t=x+y-z;
            int u=x-y+z;
            int v=x-y-z;
            t+=m;
            u+=m;
            v+=2*m;
            events.push_back(Event3D(s, t, u, v, 0));
            events.push_back(Event3D(s-d, t, u, v, 1));
        }
        m*=3;
        sort(events.begin(), events.end());
        for(auto e : events) {
            if(e.exiting) {
                update3(e.y, e.z, e.w, -1);
            } else {
                ans+=query3(e.y-d, e.z-d, e.w-d, e.y+d, e.z+d, e.w+d);
                update3(e.y, e.z, e.w, 1);
            }
        }
    }
    cout << ans << endl;
}

• 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