oj.uz

Submission #797334

# Submission time Handle Problem Language Result Execution time Memory
797334 2023-07-29T09:27:56 Z radaiosm7 New Home (APIO18_new_home) C++
0 / 100
 67 ms 38440 KB 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, q, k, i, x, t, a, b, ans, MXM;
bool ok;
pair<pair<int, int>, pair<int, int> > shops[300005];

struct Node {
  int val;
  Node *l, *r;

  Node(int x) : val(x), l(nullptr), r(nullptr) {}

  Node(Node *ll, Node *rr) {
    val = 0;
    l = ll;
    r = rr;
    if (l) val += l->val;
    if (r) val += r->val;
  }

  Node(Node *cp) : val(cp->val), l(cp->l), r(cp->r) {};
};

vector<Node*> heads[300005];
vector<int> times[300005];

Node *Update(Node *node, int pos, int val, int l=1, int r=MXM) {
  if (l == r) return new Node(node->val+val);
  int mid = (l+r)/2;
  
  if (pos <= mid) {
    if (node->l == nullptr) node->l = new Node(0);
    return new Node(Update(node->l, pos, val, l, mid), node->r);
  }

  else {
    if (node->r == nullptr) node->r = new Node(0);
    return new Node(node->l, Update(node->r, pos, val, mid+1, r));
  }
}

int Query(Node *node, int from, int to, int l=1, int r=MXM) {
  if (node == nullptr) return 0;
  if (from == l && to == r) return node->val;
  int mid = (l+r)/2;

  if (to <= mid) return Query(node->l, from, to, l, mid);
  else if (from > mid) return Query(node->r, from, to, mid+1, r);
  else return Query(node->l, from, mid, l, mid) + Query(node->r, mid+1, to, mid+1, r);
}

int Walk(Node *node, int kval, int l=1, int r=MXM) {
  if (l == r) return l;
  int mid = (l+r)/2;
  if (node->l == nullptr) return Walk(node->r, kval, mid+1, r);
  else if ((node->l)->val < kval) return Walk(node->r, kval-(node->l)->val, mid+1, r);
  else return Walk(node->l, kval, l, mid);
}


int main() {
  scanf("%d%d%d", &n, &k, &q);
  MXM = 0;

  for (i=0; i < n; ++i) {
    scanf("%d%d%d%d", &x, &t, &a, &b);
    MXM = max(MXM, x);
    shops[2*i] = make_pair(make_pair(a, 1), make_pair(x, t));
    shops[2*i+1] = make_pair(make_pair(b+1, -1), make_pair(x, t));
  }

  sort(shops, shops+2*n);
  
  for (i=1; i <= k; ++i) {
    heads[i].push_back(new Node(0));
    times[i].push_back(0);
  }

  for (i=0; i < 2*n; ++i) {
    t = shops[i].Y.Y;
    x = shops[i].Y.X;
    a = shops[i].X.X;
    b = shops[i].X.Y;
    heads[t].push_back(Update(heads[t].back(), x, b));
    times[t].push_back(a);
  }
  
  while(q--) {
    scanf("%d%d", &a, &b);
    ok = true;
    ans = 0;

    for (i=1; i <= k; ++i) {
      t = prev(upper_bound(times[i].begin(), times[i].end(), b))-times[i].begin();

      if (Query(heads[i][t], 1, MXM) == 0) {
        ok = false;
        break;
      }
      
      if (Query(heads[i][t], a, a) == 0) {
        int d1 = 100000005;
        int d2 = 100000005;
        int q1 = Query(heads[i][t], 1, a-1);
        if (q1 > 0) d1 = a-Walk(heads[i][t], q1);
        int q2 = Query(heads[i][t], a+1, MXM);
        if (q2 > 0) d2 = Walk(heads[i][t], q1+1)-a;
        d1 = min(d1, d2);
        ans = max(ans, d1);
      }
    }

    if (!ok) printf("-1\n");
    else printf("%d\n", ans);
  }

  return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d%d%d", &n, &k, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d%d%d%d", &x, &t, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d%d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14296 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 14 ms 14536 KB Output is correct
6 Correct 15 ms 15308 KB Output is correct
7 Correct 9 ms 15408 KB Output is correct
8 Correct 9 ms 15440 KB Output is correct
9 Correct 11 ms 15388 KB Output is correct
10 Incorrect 11 ms 15312 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14296 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 14 ms 14536 KB Output is correct
6 Correct 15 ms 15308 KB Output is correct
7 Correct 9 ms 15408 KB Output is correct
8 Correct 9 ms 15440 KB Output is correct
9 Correct 11 ms 15388 KB Output is correct
10 Incorrect 11 ms 15312 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 38388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 38440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14296 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 14 ms 14536 KB Output is correct
6 Correct 15 ms 15308 KB Output is correct
7 Correct 9 ms 15408 KB Output is correct
8 Correct 9 ms 15440 KB Output is correct
9 Correct 11 ms 15388 KB Output is correct
10 Incorrect 11 ms 15312 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14296 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 14 ms 14536 KB Output is correct
6 Correct 15 ms 15308 KB Output is correct
7 Correct 9 ms 15408 KB Output is correct
8 Correct 9 ms 15440 KB Output is correct
9 Correct 11 ms 15388 KB Output is correct
10 Incorrect 11 ms 15312 KB Output isn't correct
11 Halted 0 ms 0 KB -