Submission #261201

#	Time	Username	Problem	Language	Result	Execution time	Memory
261201		stoyan_malinin	Pairs (IOI07_pairs)	C++14	100 / 100	2094 ms	297396 KiB

pairs

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

int b, n, d, m;

void arbeit1()
{
    vector <int> v;
    for(int i = 0;i<n;i++)
    {
        int x;
        cin >> x;

        v.push_back(x);
    }

    long long answer = 0;
    sort(v.begin(), v.end());

    for(int i = 0;i<n-1;i++)
    {
        if(v[i+1]-v[i]>d) continue;

        int l = i + 1, r = n - 1, mid;
        while(l+1<r)
        {
            mid = (l+r)/2;

            if(v[mid]-v[i]<=d) l = mid;
            else r = mid - 1;
        }

        if(v[r]-v[i]<=d) answer += r - i;
        else answer += l - i;
    }

    cout << answer << '\n';
}

struct Plane2D
{
    int offset;

    Plane2D(){}
    Plane2D(int offset)
    {
        this->offset = offset;
    }

    struct Event
    {
        int type; //1 -> left square side, point, right square side
        int pos, height;

        int l, r;

        Event(){}
        Event(int type, int pos)
        {
            this->type = type;
            this->pos = pos;
        }
        Event(int type, int pos, int height) : Event(type, pos)
        {//offset?
            this->height = height;
        }
        Event(int type, int pos, int l, int r) : Event(type, pos)
        {//offset?
            this->l = l;
            this->r = r;
        }

        bool operator <(Event other)
        {
            if(pos!=other.pos) return pos<other.pos;
            return type<other.type;
        }
    };
    vector <Event> v;

    struct FenwickTree
    {
        int n;
        vector <int> tree;

        FenwickTree(){}
        FenwickTree(int sz)
        {
            tree.assign(sz+10, 0);
            this->n = sz + 3;
        }

        void update(int ind, int val)
        {
            ind++;
            while(ind<n)
            {
                tree[ind] += val;
                ind += ind&(-ind);
            }
        }

        int query(int ind)
        {
            int sum = 0;

            ind++;
            while(ind>0)
            {
                sum += tree[ind];
                ind -= ind&(-ind);
            }

            return sum;
        }

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

    void addPoint(int x, int y)
    {
        v.push_back(Event(2, x, y+offset));
    }

    void addSquare(pair <int, int> centre, int side)
    {
        v.push_back(Event(1, centre.first-side, centre.second-side+offset, centre.second+side+offset));
        v.push_back(Event(3, centre.first+side, centre.second-side+offset, centre.second+side+offset));
    }

    long long process()
    {
        long long answer = 0;

        int maxCoordinate = 0;
        for(Event e: v)
        {
            if(e.type==2) maxCoordinate = max(maxCoordinate, e.height);
            if(e.type==1) maxCoordinate = max(maxCoordinate, e.r);
        }

        sort(v.begin(), v.end());
        FenwickTree T(maxCoordinate);

        for(Event e: v)
        {
            //cout << e.pos << " ";

            if(e.type==1)
            {
                //cout << e.type << " -- " << e.l << " " << e.r << '\n';
                answer -= T.query(e.l, e.r);
            }
            else if(e.type==2)
            {
                //cout << e.type << " -- " << e.height << '\n';
                T.update(e.height, +1);
            }
            else if(e.type==3)
            {
                //cout << e.type << " -- " << e.l << " " << e.r << '\n';
                answer += T.query(e.l, e.r);
            }
        }

        return answer;
    }
};

void arbeit2()
{
    int offset = 0;
    vector <pair <int, int>> v;

    for(int i = 0;i<n;i++)
    {
        int x, y;
        cin >> x >> y;

        v.push_back({x+y, x-y});
        if(x-y-d<0) offset = max(offset, -(x-y-d));
    }

    Plane2D P(offset);
    for(pair <int, int> p: v)
    {
        P.addPoint(p.first, p.second);
        P.addSquare(p, d);
    }

    cout << (P.process()-n)/2 << '\n';
}

Plane2D P[80];
void arbeit3()
{
    for(int i = 1;i<=m;i++) P[i] = Plane2D(200);
    for(int i = 0;i<n;i++)
    {
        int x, y, z;
        cin >> x >> y >> z;

        for(int p = 1;p<=m;p++)
        {
            if(abs(p-z)>d) continue;
            P[p].addSquare({x+y, x-y}, d-abs(p-z));
        }

        P[z].addPoint(x+y, x-y);
    }

    long long answer = 0;
    for(int i = 1;i<=m;i++) answer += P[i].process();

    cout << (answer-n)/2 << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> b >> n >> d >> m;

    if(b==1) arbeit1();
    else if(b==2) arbeit2();
    else if(b==3) arbeit3();
}

• 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