Submission #115332

#	Time	Username	Problem	Language	Result	Execution time	Memory
115332		model_code	Hotel (CEOI11_hot)	C++17	100 / 100	612 ms	20160 KiB

hot

/* 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 (stderr)

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 / 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
• Subtask 10: 10 / 10