oj.uz

Submission #368375

# Submission time Handle Problem Language Result Execution time Memory
368375 2021-02-20T01:51:49 Z TosakaUCW Unija (COCI17_unija) C++17
80 / 100
 701 ms 65540 KB 
#include <stdio.h>
#include <algorithm>
#include <memory.h>

#define int long long

int read(int x = 0, int f = 0, char ch = getchar())
{
    while ('0' > ch or ch > '9')
        f = ch == '-', ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

const int N = 2e6 + 5;

int n, cnt, maxn;
int raw[N], c[N];
int ans;

struct Node
{
    int x, y1, y2, opt;
} line[N];
struct node
{
    int L, R, cnt, len;
} tree[N << 4];

bool cmp(Node A, Node B) { return A.x == B.x ? A.opt > B.opt : A.x < B.x; }

void build(int p, int L, int R)
{
    tree[p].L = L, tree[p].R = R;
    if (L == R)
        return;
    int mid = (tree[p].L + tree[p].R) / 2;
    build(p * 2, L, mid), build(p * 2 + 1, mid + 1, R);
}

void push(int p)
{
    if (tree[p].cnt >= 1)
        tree[p].len = raw[tree[p].R + 1] - raw[tree[p].L];
    else
        tree[p].len = tree[p * 2].len + tree[p * 2 + 1].len;
}

void add(int p, int L, int R, int val)
{
    if (L <= tree[p].L and tree[p].R <= R)
    {
        tree[p].cnt += val;
        push(p);
        return;
    }
    int mid = (tree[p].L + tree[p].R) / 2;
    if (L <= mid)
        add(p * 2, L, R, val);
    if (mid < R)
        add(p * 2 + 1, L, R, val);
    push(p);
}

signed main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {

        int x1, x2, y1, y2;
        int x = read(), y = read();
        x2 = x / 2, x1 = -x2, y2 = y / 2, y1 = -y2;
        line[i * 2 - 1] = Node{x1, y1, y2, 1};
        line[i * 2] = Node{x2, y1, y2, -1};
        raw[++cnt] = y1, raw[++cnt] = y2;
    }
    std::sort(raw + 1, raw + 1 + cnt);
    cnt = std::unique(raw + 1, raw + 1 + cnt) - raw - 1;
    for (int i = 1; i <= 2 * n; i++)
    {
        int pos1 = std::lower_bound(raw + 1, raw + cnt + 1, line[i].y1) - raw;
        int pos2 = std::lower_bound(raw + 1, raw + cnt + 1, line[i].y2) - raw;
        line[i].y1 = pos1, line[i].y2 = pos2;
    }
    std::sort(line + 1, line + 1 + 2 * n, cmp);
    build(1, 1, cnt);
    for (int i = 1; i <= 2 * n; i++)
    {
        add(1, line[i].y1, line[i].y2 - 1, line[i].opt);
        ans += (line[i + 1].x - line[i].x) * tree[1].len;
    }
    printf("%lld", ans);
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6852 KB Output is correct
2 Correct 57 ms 6892 KB Output is correct
3 Correct 64 ms 6764 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 24596 KB Output is correct
2 Correct 218 ms 24684 KB Output is correct
3 Correct 216 ms 24556 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 56812 KB Output is correct
2 Correct 701 ms 56812 KB Output is correct
3 Correct 700 ms 56812 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -