Submission #59286

#	Time	Username	Problem	Language	Result	Execution time	Memory
59286		Just_Solve_The_Problem	New Home (APIO18_new_home)	C++11	12 / 100	2780 ms	118444 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

const int N = (int)3e5 + 7;
const int inf = (int)1e9 + 7;

int n, k, q;
int x[N], t[N], a[N], b[N];
multiset < int > s[404];
int ans[N];

struct query {
  int type, x, t, y, ind;
  query() {}
  query(int _type, int _x, int _t, int _y) {
    type = _type;
    x = _x;
    t = _t;
    y = _y;
  }
};
vector < query > vec;

bool cmp(query &A, query &B) {
  if (A.y != B.y)
    return A.y < B.y;
  return A.type < B.type;
}

main() {
	scanf("%d %d %d", &n, &k, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d %d", &x[i], &t[i], &a[i], &b[i]);
    vec.pb(query(0, x[i], t[i], a[i]));
    vec.pb(query(1, x[i], t[i], b[i] + 1));
  }
  for (int i = 1, l, y; i <= q; i++) {
    scanf("%d %d", &l, &y);
    vec.pb(query(2, l, 0, y));
    vec.back().ind = i;
  }
  sort(all(vec), cmp);
  for (auto to : vec) {
    if (to.type == 0) {
      s[to.t].insert(to.x);
    } else if (to.type == 1) {
      s[to.t].erase(s[to.t].find(to.x));
    } else {
      int res = -1;
      for (int i = 1; i <= k; i++) {
        if (s[i].empty()) {
          res = -1;
          break;
        } else {
          auto it = s[i].lower_bound(to.x);
          int asd = inf;
          if (it != s[i].end())
            asd = min(asd, abs(to.x - (*it)));
          if (it != s[i].begin()) {
            it--;
            asd = min(asd, abs(to.x - (*it)));
          }
          res = max(res, asd);
        }
      }
      ans[to.ind] = res;
    }
  }
  for (int i = 1; i <= q; i++) {
    printf("%d\n", ans[i]);
  }
}

Compilation message (stderr)

new_home.cpp:39:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
new_home.cpp: In function 'int main()':
new_home.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &x[i], &t[i], &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &l, &y);
     ~~~~~^~~~~~~~~~~~~~~~~

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