Submission #658967

#	Time	Username	Problem	Language	Result	Execution time	Memory
658967		600Mihnea	New Home (APIO18_new_home)	C++17	0 / 100	53 ms	98864 KiB

new_home

bool home = 1;

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct T {
  int x;
  int t;
  int a;
  int b;
};

struct U {
  int pos;
  int x;
};

struct Q {
  int x;
  int t;
};


const int N = (int) 3e5 + 7;
const int TM = 3 * N;
const int INF = (int) 1e9 + 7;
int n;
int k;
int q;
int maxtime;
T v[N];
multiset<int> active[N];
map<int, vector<int>> MPevents;
map<int, int> interestingTimesMap;

vector<int> tree[4 * TM];

int main() {
  if (home == 0) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  } else {
    freopen ("input.txt", "r", stdin);
  }

  cin >> n >> k >> q;

  for (int i = 1; i <= n; i++) {
    cin >> v[i].x >> v[i].t >> v[i].a >> v[i].b;
    v[i].x *= 2;
    MPevents[v[i].a].push_back(+i);
    MPevents[v[i].b + 1].push_back(-i);
    interestingTimesMap[v[i].a] = 0;
    interestingTimesMap[v[i].b + 1] = 0;
  }

  for (int tp = 1; tp <= k; tp++) {
    active[tp].insert(+((int) 2e8));
    active[tp].insert(-((int) 2e8));
  }

  vector<Q> qs(q);

  for (int iq = 0; iq < q; iq++) {
    cin >> qs[iq].x >> qs[iq].t;
    qs[iq].x *= 2;
    interestingTimesMap[qs[iq].t] = 0;
  }

  {
    maxtime = 0;
    for (auto &it : interestingTimesMap) {
      it.second = ++maxtime;
    }
    for (int i = 1; i <= n; i++) {
      v[i].a = interestingTimesMap[v[i].a];
      v[i].b = interestingTimesMap[v[i].b + 1] - 1;
    }
    for (int iq = 0; iq < q; iq++) {
      qs[iq].t = interestingTimesMap[qs[iq].t];
    }
  }




  return 0;

  cout << "interestingTimesSet = ";
  for (auto &t : interestingTimesMap) {
    cout << t.first << " ";
  }
  cout << "\n";

  return 0;

/*
  for (auto &IT : events) {
    int a = IT.first;
    vector<int> events = IT.second;
    for (auto &i : events) {
      if (i >= 1) {
        assert(1 <= i && i <= n);
        /// add i

      } else {
        i *= -1;
        assert(1 <= i && i <= n);

        /// delete i
      }
    }
  }*/

/*
  vector<int> sol(q, 0);

  vector<U> lft, rgh;

  for (int tp = 1; tp <= k; tp++) {
    if (gs[tp].empty()) {
      continue;
    }
    sort(gs[tp].begin(), gs[tp].end(), [&] (int i, int j) {
      return v[i].x < v[j].x;
    });
    for (int i = 0; i + 1 < (int) gs[tp].size(); i++) {
      T cur = v[gs[tp][i]];
      T nxt = v[gs[tp][i + 1]];
      lft.push_back({(cur.x + nxt.x) / 2, cur.x});
      rgh.push_back({(cur.x + nxt.x) / 2, nxt.x});
    }
    rgh.push_back({-(int) 2e8, v[gs[tp][0]].x});
    lft.push_back({+(int) 2e8, v[gs[tp].back()].x});
  }

  sort(rgh.begin(), rgh.end(), [&] (U a, U b) {
    return a.pos < b.pos;
  });

  {
    int mx = -((int) 1e9 + 7);
    int pt = 0;
    for (int i = 0; i < q; i++) {
      int x = qs[i].first;
      while (pt < (int) rgh.size() && rgh[pt].pos <= x) {
        mx = max(mx, rgh[pt++].x);
      }
      sol[i] = max(sol[i], mx - x);
    }
  }
  sort(lft.begin(), lft.end(), [&] (U a, U b) {
    return a.pos > b.pos;
  });

  {
    int mn = ((int) 1e9 + 7);
    int pt = 0;
    for (int i = q - 1; i >= 0; i--) {
      int x = qs[i].first;
      while (pt < (int) lft.size() && x <= lft[pt].pos) {
        mn = min(mn, lft[pt++].x);
      }
      sol[i] = max(sol[i], x - mn);
    }
  }


  for (int i = 0; i < q; i++) {
    cout << sol[inv[i]] / 2 << "\n";
  }
  return 0;

  for (int iq = 1; iq <= q; iq++) {
    int x, t;
    cin >> x >> t;
    qs.push_back({x, iq});
    int sol = -INF;
    for (int tp = 1; tp <= k; tp++) {
      int nr = INF;
      for (auto &i : gs[tp]) {
        if (v[i].a <= t && t <= v[i].b) {
          nr = min(nr, abs(x - v[i].x));
        }
      }
      sol = max(sol, nr);
    }
    if (sol == INF) {
      sol = -1;
    }
    cout << sol << "\n";
  }
  */
  return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:45:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20