oj.uz

Submission #5745

# Submission time Handle Problem Language Result Execution time Memory
5745 2014-05-15T12:21:46 Z model_code 사회적 불평등 (TOKI14_social) C++
100 / 100
 96 ms 4408 KB 
/*
 * Official Solution
 * 
 * Social Inequality
 * Derianto Kusuma
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include <math.h>

#define MAX_N        100001

int n;
long long x[MAX_N];
long long y[MAX_N];

// Merge sort temp buffer
long long xTemp[MAX_N];
long long yTemp[MAX_N];
bool isLeftDivision[MAX_N];
bool isLeftDivisionTemp[MAX_N];

void sortByX(int left, int right)
{
    if (left >= right)
        return;
        
    int p1 = left, p2 = right;
    long long pivotX = x[(left + right) / 2];
    long long temp;
    
    while (p1 < p2)
    {
        while (x[p1] < pivotX) p1++;
        while (x[p2] > pivotX) p2--;
        if (p1 < p2)
        {
            // Swap
            temp = x[p1]; x[p1] = x[p2]; x[p2] = temp;
            temp = y[p1]; y[p1] = y[p2]; y[p2] = temp;
        }
        
        if (p1 <= p2)
        {
            p1++;
            p2--;
        }
    }
    
    sortByX(left, p2);
    sortByX(p1, right);
}

long long longAbs(long long a)
{
    if (a >= 0)
        return a;
    else
        return -a;
}

void readInput()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld %lld", &x[i], &y[i]);
    }
    
    // Sort by x
    sortByX(0, n - 1);
}

void mergeSortByY(int left1, int right1, int left2, int right2)
{
    int posResult = left1;
    int pos1 = left1;
    int pos2 = left2;

    while (true)
    {
        if (pos1 <= right1 && pos2 <= right2)
        {
            if (y[pos1] <= y[pos2])
            {
                xTemp[posResult] = x[pos1]; yTemp[posResult] = y[pos1]; isLeftDivisionTemp[posResult] = isLeftDivision[pos1];
                posResult++;
                pos1++;
            }
            else
            {
                xTemp[posResult] = x[pos2]; yTemp[posResult] = y[pos2]; isLeftDivisionTemp[posResult] = isLeftDivision[pos2];
                posResult++;
                pos2++;
            }
        }
        else if (pos1 <= right1)
        {
            xTemp[posResult] = x[pos1]; yTemp[posResult] = y[pos1]; isLeftDivisionTemp[posResult] = isLeftDivision[pos1];
            posResult++;
            pos1++;
        }
        else if (pos2 <= right2)
        {
            xTemp[posResult] = x[pos2]; yTemp[posResult] = y[pos2]; isLeftDivisionTemp[posResult] = isLeftDivision[pos2];
            posResult++;
            pos2++;
        }
        else
        {
            break;
        }
    }
    
    assert(pos1 == right1 + 1);
    assert(pos2 == right2 + 1);
    assert(posResult == right2 + 1);
    
    // Copy from temp buffer to real buffer
    for (int i = left1; i <= right2; i++)
    {
        x[i] = xTemp[i];
        y[i] = yTemp[i];
        isLeftDivision[i] = isLeftDivisionTemp[i];
    }
}

long long getSumDxFromRightX(int minIndex, int maxIndex, int rightX)
{
    long long result = 0;
    for (int i = minIndex; i <= maxIndex; i++)
    {
        if (isLeftDivision[i])
        {
            result += rightX - x[i];
        }
    }
    return result;
}

long long getSumDyFromBottomY(int minIndex, int maxIndex, int bottomY)
{
    long long result = 0;
    for (int i = minIndex; i <= maxIndex; i++)
    {
        if (isLeftDivision[i])
        {
            result += y[i] - bottomY;
        }
    }
    return result;
}

long long getSumAreaToRightBottom(int minIndex, int maxIndex, int rightX, int bottomY)
{
    long long result = 0;
    for (int i = minIndex; i <= maxIndex; i++)
    {
        if (isLeftDivision[i])
        {
            result += (rightX - x[i]) * (y[i] - bottomY);
        }
    }
    return result;
}

long long rec(int minIndex, int maxIndex)
{
    if (minIndex >= maxIndex)
        return 0;
    
    int middle = (minIndex + maxIndex) / 2;
    long long middleX = x[middle];
    
    // Divide
    long long leftAnswer = rec(minIndex, middle);
    long long rightAnswer = rec(middle + 1, maxIndex);
    
    long long answer = leftAnswer + rightAnswer;
    
    // Data for merging operation
    long long nLeftBottomOfSweepLine;
    long long nLeftTopOfSweepLine;
    long long sumLeftDxBottomOfSweepLine;
    long long sumLeftDxTopOfSweepLine;
    long long sumLeftDyBottomOfSweepLine;
    long long sumLeftDyTopOfSweepLine;
    long long sumLeftAreaBottomOfSweepLine;
    long long sumLeftAreaTopOfSweepLine;
    
    int sweepLineIndex;
    long long sweepLineY;
    long long sweepLineDy;
    
    long long pointSpecificAnswer;
    
    // Set up point divisions before merging
    for (int i = minIndex; i <= maxIndex; i++)
        isLeftDivision[i] = (i <= middle);
    
    // Merge - sort by y - retaining isLeftDivision value so we can still distinguish which
    // points were originally from the left / right divisions
    mergeSortByY(minIndex, middle, middle + 1, maxIndex);
    
    // Initialize merging operation data at sweepLineY = bottom Y
    sweepLineY = y[minIndex];
    
    nLeftBottomOfSweepLine = 0;
    nLeftTopOfSweepLine = middle - minIndex + 1;
    sumLeftDxBottomOfSweepLine = 0;
    sumLeftDxTopOfSweepLine = getSumDxFromRightX(minIndex, maxIndex, middleX);
    sumLeftDyBottomOfSweepLine = 0;
    sumLeftDyTopOfSweepLine = getSumDyFromBottomY(minIndex, maxIndex, sweepLineY);
    sumLeftAreaBottomOfSweepLine = 0;
    sumLeftAreaTopOfSweepLine = getSumAreaToRightBottom(minIndex, maxIndex, middleX, sweepLineY);
    
    // Sweep from bottom to top
    for (sweepLineIndex = minIndex; sweepLineIndex <= maxIndex; sweepLineIndex++)
    {
        sweepLineY = y[sweepLineIndex];
        sweepLineDy = (sweepLineIndex == minIndex) ? 0 : sweepLineY - y[sweepLineIndex - 1];
        
        // Update operational data
        sumLeftDyBottomOfSweepLine += nLeftBottomOfSweepLine * sweepLineDy;
        sumLeftDyTopOfSweepLine -= nLeftTopOfSweepLine * sweepLineDy;
        sumLeftAreaBottomOfSweepLine += sumLeftDxBottomOfSweepLine * sweepLineDy;
        sumLeftAreaTopOfSweepLine -= sumLeftDxTopOfSweepLine * sweepLineDy;
        
        if (isLeftDivision[sweepLineIndex])
        {
            // Point is in the left division - add a point under sweep line
            sumLeftDxBottomOfSweepLine += (middleX - x[sweepLineIndex]);
            sumLeftDxTopOfSweepLine -= (middleX - x[sweepLineIndex]);
            
            nLeftBottomOfSweepLine++;
            nLeftTopOfSweepLine--;
        }
        else
        {
            // Point is in the right division - update answer
            pointSpecificAnswer =
                sumLeftAreaBottomOfSweepLine +
                sumLeftAreaTopOfSweepLine +
                sumLeftDyBottomOfSweepLine * (x[sweepLineIndex] - middleX) +
                sumLeftDyTopOfSweepLine * (x[sweepLineIndex] - middleX);
            answer += pointSpecificAnswer;
        }
    }
    
    return answer;
}

void writeOutput()
{
    long long result = rec(0, n - 1);
    printf("%lld\n", result);
}

int main()
{
    readInput();
    writeOutput();

    return 0;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4408 KB Output is correct
2 Correct 0 ms 4408 KB Output is correct
3 Correct 0 ms 4408 KB Output is correct
4 Correct 0 ms 4408 KB Output is correct
5 Correct 0 ms 4408 KB Output is correct
6 Correct 0 ms 4408 KB Output is correct
7 Correct 0 ms 4408 KB Output is correct
8 Correct 0 ms 4408 KB Output is correct
9 Correct 0 ms 4408 KB Output is correct
10 Correct 4 ms 4408 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4408 KB Output is correct
2 Correct 32 ms 4408 KB Output is correct
3 Correct 24 ms 4408 KB Output is correct
4 Correct 28 ms 4408 KB Output is correct
5 Correct 36 ms 4408 KB Output is correct
6 Correct 28 ms 4408 KB Output is correct
7 Correct 20 ms 4408 KB Output is correct
8 Correct 20 ms 4408 KB Output is correct
9 Correct 24 ms 4408 KB Output is correct
10 Correct 36 ms 4408 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4408 KB Output is correct
2 Correct 36 ms 4408 KB Output is correct
3 Correct 24 ms 4408 KB Output is correct
4 Correct 32 ms 4408 KB Output is correct
5 Correct 28 ms 4408 KB Output is correct
6 Correct 36 ms 4408 KB Output is correct
7 Correct 40 ms 4408 KB Output is correct
8 Correct 36 ms 4408 KB Output is correct
9 Correct 24 ms 4408 KB Output is correct
10 Correct 44 ms 4408 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4408 KB Output is correct
2 Correct 76 ms 4408 KB Output is correct
3 Correct 72 ms 4408 KB Output is correct
4 Correct 40 ms 4408 KB Output is correct
5 Correct 44 ms 4408 KB Output is correct
6 Correct 72 ms 4408 KB Output is correct
7 Correct 52 ms 4408 KB Output is correct
8 Correct 76 ms 4408 KB Output is correct
9 Correct 96 ms 4408 KB Output is correct
10 Correct 92 ms 4408 KB Output is correct