oj.uz

Submission #131812

# Submission time Handle Problem Language Result Execution time Memory
131812 2019-07-17T17:02:08 Z apostoldaniel854 Kisik (COCI19_kisik) C++14
90 / 90
 618 ms 32408 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5240 KB Output is correct
2 Correct 15 ms 5368 KB Output is correct
3 Correct 49 ms 3704 KB Output is correct
4 Correct 18 ms 7036 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7160 KB Output is correct
2 Correct 53 ms 7800 KB Output is correct
3 Correct 17 ms 7992 KB Output is correct
4 Correct 19 ms 1528 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4856 KB Output is correct
2 Correct 10 ms 2936 KB Output is correct
3 Correct 45 ms 7160 KB Output is correct
4 Correct 47 ms 3448 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6324 KB Output is correct
2 Correct 27 ms 7672 KB Output is correct
3 Correct 16 ms 4344 KB Output is correct
4 Correct 33 ms 7928 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 18416 KB Output is correct
2 Correct 398 ms 25320 KB Output is correct
3 Correct 338 ms 24996 KB Output is correct
4 Correct 311 ms 23768 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 21120 KB Output is correct
2 Correct 55 ms 13688 KB Output is correct
3 Correct 98 ms 15452 KB Output is correct
4 Correct 268 ms 22264 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 17220 KB Output is correct
2 Correct 380 ms 23680 KB Output is correct
3 Correct 285 ms 20088 KB Output is correct
4 Correct 531 ms 32408 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 18680 KB Output is correct
2 Correct 618 ms 31216 KB Output is correct
3 Correct 183 ms 17784 KB Output is correct
4 Correct 383 ms 26508 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 25984 KB Output is correct
2 Correct 386 ms 25124 KB Output is correct
3 Correct 322 ms 22396 KB Output is correct
4 Correct 185 ms 18808 KB Output is correct