oj.uz

Submission #115332

# Submission time Handle Problem Language Result Execution time Memory
115332 2019-06-06T17:24:41 Z model_code Hotel (CEOI11_hot) C++17
100 / 100
 612 ms 20160 KB 
/* Model solution for task HOT
 * Author: Miroslaw Michalski
 * Time complexity : O(n log n)
 * 22MAY11
 * no maps!
 */
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

struct FAU {
    int *p;
    FAU(int s) {
      p = new int[s];
	    for(int x = 0; x < s; x++) p[x]=-1;
    }
    ~FAU() {delete[] p;}
    int Find(int x) {
      return (p[x] < 0) ? x : p[x]=Find(p[x]);
    }
    void Union(int x, int y) {
      x=Find(x); y=Find(y);
      if (x==y) return;
    	if (p[x] > p[y]) p[y] = x; else {
        p[x] = y;
      }
    }
};

int main() {
  int n, m, o, ci, pi;
  long long res = 0;
  vector<int> think;
  vector<pair<int, int> > vtmp;
  vector<pair<pair<int, int>, int> > fau;
  scanf("%d%d%d", &n, &m, &o);
  for(int i = 0; i < n; i++) {
    scanf("%d%d", &ci, &pi);
    pair<int, int> obj = make_pair(pi, ci);
    vtmp.push_back(obj);
  }
  sort(vtmp.begin(), vtmp.end());

  pair<int, int> prev = vtmp[0];
  int cnt = 1;
  for(size_t i = 1; i < vtmp.size(); i++) {
    if (vtmp[i] != prev) {
     fau.push_back(make_pair(prev, cnt));
     prev = vtmp[i];
     cnt = 1;
    } else {
      cnt++;
    }
  }
  fau.push_back(make_pair(prev, cnt));
  
  int fauSize = fau.size();
  FAU f(fauSize);

  vector<pair<int, int> > q;
  for(int i = 0; i < m; i++) {
    scanf("%d%d", &ci, &pi);
    q.push_back(make_pair(ci, pi));
  }
  sort(q.begin(), q.end());
  reverse(q.begin(), q.end());
  
  for(int i = 0; i < m; i++) {
    ci = q[i].first;
    pi = q[i].second;
    pair<int, int> target = make_pair(pi, -1);
    int be = 0, en = fauSize - 1;
    while (be < en) {
      int mid = be + (en - be) / 2;
      int realMidPos = f.Find(mid);
      pair<pair<int, int>, int> obj = fau[realMidPos];
      if (obj.first < target) {
        be = mid + 1;
      } else {
        en = mid;
      }
    }
    int realBePos = f.Find(be);
    pair<pair<int, int>, int> offer = fau[realBePos];
    if (offer.second > 0 && offer.first > target) {
      if (offer.first.second < ci) {
        think.push_back(ci - offer.first.second);
        if (offer.second == 1) {
          fau[realBePos].second = 0;
          if (realBePos < fauSize - 1) {
            f.Union(realBePos, realBePos + 1);
          } else {
            fauSize--;
          }
        } else {
          fau[realBePos].second--;
        }
      }
    }
  }
  sort(think.begin(), think.end());
  reverse(think.begin(), think.end());
  o = min(o, static_cast<int>(think.size()));
  for(int i = 0; i < o; i++) {
    res += think[i];
  }
  printf("%lld\n", res);
  return 0;
}

Compilation message

hot.cpp: In function 'int main()':
hot.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &m, &o);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
hot.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &ci, &pi);
     ~~~~~^~~~~~~~~~~~~~~~~~
hot.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &ci, &pi);
     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 768 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2028 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3536 KB Output is correct
2 Correct 49 ms 3180 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 8700 KB Output is correct
2 Correct 119 ms 5624 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 16996 KB Output is correct
2 Correct 421 ms 17040 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 15740 KB Output is correct
2 Correct 563 ms 20160 KB Output is correct
3 Correct 612 ms 20052 KB Output is correct