Submission #131812

#	Time	Username	Problem	Language	Result	Execution time	Memory
131812		apostoldaniel854	Kisik (COCI19_kisik)	C++14	90 / 90	618 ms	32408 KiB

kisik

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6;

struct house {
  int h; int w;
};
#define ll long long
house a[MAXN + 1];
int aib1[MAXN + 1];
ll aib2[MAXN + 1];

void add1 (int val, int x) {
  do {
    aib1[x] += val;
    x += x & -x;
  } while (x <= MAXN);
}

int get1 (int x) {
  int s = 0;
  while (x) {
    s += aib1[x];
    x &= x - 1;
  }
  return s;
}

void add2 (int val, int x) {
  do {
    aib2[x] = aib2[x] + val;
    x += x & -x;
  } while (x <= MAXN);
}

ll get2 (int x) {
  ll s = 0;
  while (x) {
    s += aib2[x];
    x &= x - 1;
  }
  return s;
}
int find1 (int val) {
  int x = 0;
  int interval = (1 << 19);
  while (interval) {
    if (x + interval <= MAXN && aib1[x + interval] < val) {
      val -= aib1[x + interval];
      x += interval;
    }
    interval >>= 1;
  }
  return x;
}



bool cmp1 (house a, house b) {
  return a.h < b.h;
}

int main() {
  int n, k, i, maxh, j, st, dr, mij;

 // freopen ("input", "r", stdin);
 // freopen ("output", "w", stdout);

  scanf ("%d", &n);
  scanf ("%d", &k);

  maxh = 0;

  for (i = 1; i <= n; i++) {
    scanf ("%d%d", &a[i].w, &a[i].h);
    maxh = max (maxh, a[i].h);
  }

  sort (a + 1, a + n + 1, cmp1);

  /*for (i = 1; i <= n; i++)
    printf ("%d %d\n", a[i].w, a[i].h);
*/
  ll sol;
  sol = 1e18;
  j = 1;
int   maxw = 0;
  for (i = 1; i <= maxh; i++) {
    while (j <= n && a[j].h == i) {
      maxw = max (maxw, a[j].w);
      add1 (1, a[j].w);
      add2 (a[j].w, a[j].w);
      j++;
    }

    //printf ("%d\n", j);
    if (j > k) {
      /*st = 1;
      dr = maxw;
      ll to = maxw;
      while (st <= dr) {
        mij = (st + dr) / 2;
        if (get1 (mij) < k) {
          to = mij;
          st = mij + 1;
        }
        else {
          dr = mij - 1;
        }
      }*/
      ll to = find1 (k);
      //printf ("tnt %lld\n", to);
      ll lenght = get2 (to) + (k - get1 (to)) * (to + 1);
      sol = min (sol, lenght * i);
    }
  }

  printf ("%lld\n", sol);
  return 0;
}

Compilation message (stderr)

kisik.cpp: In function 'int main()':
kisik.cpp:66:25: warning: unused variable 'st' [-Wunused-variable]
   int n, k, i, maxh, j, st, dr, mij;
                         ^~
kisik.cpp:66:29: warning: unused variable 'dr' [-Wunused-variable]
   int n, k, i, maxh, j, st, dr, mij;
                             ^~
kisik.cpp:66:33: warning: unused variable 'mij' [-Wunused-variable]
   int n, k, i, maxh, j, st, dr, mij;
                                 ^~~
kisik.cpp:71:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &n);
   ~~~~~~^~~~~~~~~~
kisik.cpp:72:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &k);
   ~~~~~~^~~~~~~~~~
kisik.cpp:77:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d%d", &a[i].w, &a[i].h);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10