Submission #401363

#TimeUsernameProblemLanguageResultExecution timeMemory
401363wnsduds1Schools (IZhO13_school)C11
5 / 100
176 ms11968 KiB
#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)

school.c: In function 'main':
school.c:21:12: warning: unused variable 'k' [-Wunused-variable]
   21 |  int i, j, k;
      |            ^
school.c:21:9: warning: unused variable 'j' [-Wunused-variable]
   21 |  int i, j, k;
      |         ^
school.c:18:7: warning: unused variable 'tmp' [-Wunused-variable]
   18 |  list tmp;
      |       ^~~
school.c:23:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   23 |  scanf("%d %d %d", &n, &m, &s);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.c:26:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   26 |   scanf("%d %d", &value.l, &value.r);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...