oj.uz

Submission #261185

# Submission time Handle Problem Language Result Execution time Memory
261185 2020-08-11T13:37:23 Z stoyan_malinin Pairs (IOI07_pairs) C++14
60 / 100
 84 ms 13168 KB 
#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';
}

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

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

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

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1024 KB Output is correct
2 Correct 21 ms 1024 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 992 KB Output is correct
2 Correct 29 ms 1024 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1024 KB Output is correct
2 Correct 29 ms 1024 KB Output is correct
3 Correct 29 ms 1064 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12044 KB Output is correct
2 Correct 60 ms 12644 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 12104 KB Output is correct
2 Correct 71 ms 12908 KB Output is correct
3 Correct 76 ms 12896 KB Output is correct
4 Correct 68 ms 12780 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 12004 KB Output is correct
2 Correct 84 ms 13156 KB Output is correct
3 Correct 78 ms 13168 KB Output is correct
4 Correct 76 ms 13164 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -