# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
401363 | wnsduds1 | Schools (IZhO13_school) | C11 | 176 ms | 11968 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
typedef struct list {
int num;
int l, r;
}list;
void insert(list *x, list value, int ver);
list del(list *x, int ver);
void compare(list *x, list *y, list value, int ver);
int bottom_x = 0;
int bottom_y = 0;
int m, s;
int c[300001] = { 0, };
int main()
{
list arr[300001];
list x[300001];
list y[300001];
list tmp;
list value1,value2,value;
int n;
int i, j, k;
long long sum = 0;
scanf("%d %d %d", &n, &m, &s);
for (i = 0; i < n; i++)
{
scanf("%d %d", &value.l, &value.r);
value.num = i;
arr[i] = value;
insert(x, value, 1);
insert(y, value, 2);
}
while (m != 0 || s != 0)
{
if (m > 0)
{
value1 = del(x, 1);
if (c[value1.num] != 0)
{
compare(x, y, value1,1);
}
else {
c[value1.num] = 1;
m -= 1;
}
}
if (s > 0)
{
value2 = del(y, 2);
if (c[value2.num] != 0)
{
compare(x, y, value1,2);
}
else {
c[value2.num] = 2;
s -= 1;
}
}
}
for (i = 0; i < n; i++)
{
if (c[i] != 0)
{
if (c[i] == 1)
{
sum += (long long)arr[i].l;
}
else {
sum += (long long)arr[i].r;
}
}
}
printf("%lld", sum);
return 0;
}
void compare(list *x, list *y, list value,int ver)
{
list value1, value2;
value1 = del(x, 1);
value2 = del(y, 2);
if (ver == 1)
{
if (value.l + value1.r > value.r + value2.l)
{
c[value.num] = 2;
c[value1.num] = 1;
m -= 1;
insert(y, value2, 2);
}
else {
c[value.num] = 1;
c[value2.num] = 2;
m -= 1;
insert(x, value1, 1);
}
}
else {
if (value.l + value2.r > value.r + value1.l)
{
c[value.num] = 1;
c[value2.num] = 2;
s -= 1;
insert(x, value1, 1);
}
else {
c[value.num] = 2;
c[value1.num] = 1;
s -= 1;
insert(y, value2, 2);
}
}
}
void insert(list *x, list value, int ver)
{
if (ver == 1)
{
if (bottom_x == 0)
{
bottom_x += 1;
x[bottom_x] = value;
}
else {
int index;
list tmp;
bottom_x += 1;
x[bottom_x] = value;
index = bottom_x;
while (index != 1 && x[index].l > x[index / 2].l)
{
tmp = x[index];
x[index] = x[index / 2];
x[index / 2] = tmp;
index /= 2;
}
}
}
else {
if (bottom_y == 0)
{
bottom_y += 1;
x[bottom_y] = value;
}
else {
int index;
list tmp;
bottom_y += 1;
x[bottom_y] = value;
index = bottom_y;
while (index != 1 && x[index].r > x[index / 2].r)
{
tmp = x[index];
x[index] = x[index / 2];
x[index / 2] = tmp;
index /= 2;
}
}
}
}
list del(list *x, int ver)
{
list tmp;
list return_value;
int index = 1;
if (ver == 1)
{
return_value = x[index];
x[index] = x[bottom_x];
bottom_x -= 1;
while ((index * 2 <= bottom_x) && (x[index].l < x[index * 2].l || x[index].l < x[index * 2 + 1].l))
{
if (x[index * 2].l < x[index * 2 + 1].l)
{
tmp = x[index];
x[index] = x[index * 2 + 1];
x[index * 2 + 1] = tmp;
index = index * 2 + 1;
}
else {
tmp = x[index];
x[index] = x[index * 2];
x[index * 2] = tmp;
index = index * 2;
}
}
}
else {
return_value = x[index];
x[index] = x[bottom_y];
bottom_y -= 1;
while ((index * 2 <= bottom_y) && (x[index].r < x[index * 2].r ||x[index].r < x[index * 2 + 1].r))
{
if (x[index * 2].r < x[index * 2 + 1].r)
{
tmp = x[index];
x[index] = x[index * 2 + 1];
x[index * 2 + 1] = tmp;
index = index * 2 + 1;
}
else {
tmp = x[index];
x[index] = x[index * 2];
x[index * 2] = tmp;
index = index * 2;
}
}
}
return return_value;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |