oj.uz

Submission #829653

# Submission time Handle Problem Language Result Execution time Memory
829653 2023-08-18T13:48:10 Z erdemkiraz New Home (APIO18_new_home) C++17
33 / 100
 1455 ms 154244 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int N = 3e5 + 5;
const int OUT = 0, QUE = 1;
const int addPositive = 0, addNegative = 1;

int n, q, k, total;
int ans[N];
map<int, int> s[N];

int z, g;

int tree[2][N << 1];

int curX;
vector<pair<int, pair<int *, int>>> changes;

void update(int t, int l, int r, int x) {
  for (l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
    if ((l & 1) and x > tree[t][l]) {
      changes.push_back({curX, {&tree[t][l], tree[t][l]}});
      tree[t][l] = x;
    }
    if ((~r & 1) and x > tree[t][r]) {
      changes.push_back({curX, {&tree[t][r], tree[t][r]}});
      tree[t][r] = x;
    }
  }
}

int get(int t, int x) {
  int res = -1e9;
  x += N;
  while (x >= 1) {
    res = max(res, tree[t][x]);
    x >>= 1;
  }
  return res;
}

inline int read() {
  char c = getchar();
  int x = 0;
  while (c < '0' or c > '9')
    c = getchar();
  while ('0' <= c and c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x;
}

vector<pair<ii, int>> M[N * 4];
int isany[N * 4];

bool create(int x, int type, int l, int r, int x1, int x2, int v, int y) {
  if (x2 < l or r < x1)
    return false;
  if (type == QUE)
    isany[x] = 1;
  if (x1 <= l and r <= x2) {
    // printf("type = %d l = %d r = %d\n", type, l, r);
    M[x].push_back({{type, v}, y});
    return type == OUT;
  }
  int m = (l + r) >> 1;
  if (create(x + x, type, l, m, x1, x2, v, y)) {
    return true;
  }
  return create(x + x + 1, type, m + 1, r, x1, x2, v, y);
}

vector<int> ques;
int rid(int x) {
  return lower_bound(ques.begin(), ques.end(), x) - ques.begin() + 1;
}
int lid(int x) {
  return upper_bound(ques.begin(), ques.end(), x) - ques.begin();
}

vector<int> ins;
int ri(int x) {
  return lower_bound(ins.begin(), ins.end(), x) - ins.begin() + 1;
}
int li(int x) {
  return upper_bound(ins.begin(), ins.end(), x) - ins.begin();
}

bool solve(int x, int l, int r) {
  // if(!isany[x])
  // return;

  int delTotal = 0;

  curX = x;

  bool HARD_FAIL = 0;

  for (auto tmp : M[x]) {
    int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
    if (type == OUT) {
      if (--s[t][x])
        continue;
      s[t].erase(x);
      // printf("deleting location = %d type = %d\n", x, t);
      auto it = s[t].begin();
      int nxt = (it = s[t].upper_bound(x)) == s[t].end() ? -1 : it->first;
      int bef = (it = s[t].lower_bound(x)) == s[t].begin() ? -1 : (--it)->first;
      if (bef == -1 and nxt == -1) {
        HARD_FAIL = 1;
      } else if (bef == -1) {
        update(addNegative, 1, lid((x + nxt) / 2), nxt);
      } else if (nxt == -1) {
        update(addPositive, rid((bef + x) / 2 + 1), z, -bef);
      } else {
        update(addPositive, rid((bef + x) / 2 + 1), lid((bef + nxt) / 2), -bef);
        update(addNegative, rid((bef + nxt) / 2 + 1), lid((x + nxt) / 2), nxt);
      }
    }
  }

  if (HARD_FAIL) {
    return true;
  }

  // if(HARD_FAIL) {
  //     for(auto tmp : M[x]) {
  //         int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
  //         if(type == OUT) {
  //             // printf("reverting x = %d t = %d\n", x, t);
  //             s[t][x]++;
  //         }
  //     }

  //     while(!changes.empty() and changes.back().first == x) {
  //         *changes.back().second.first = changes.back().second.second;
  //         changes.pop_back();
  //     }
  //     return;
  // }

  if (l == r) {
    for (auto tmp : M[x]) {
      int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
      if (type == QUE) {
        int a = get(0, rid(x));
        int b = get(1, rid(x));
        // printf("que x = %d i = %d a = %d b = %d\n", x, t, a, b);
        ans[t] = max(a + x, b - x);
      }
    }
    return false;
  }

  int m = (l + r) >> 1;
  if (solve(x + x, l, m)) {
    return true;
  }
  return solve(x + x + 1, m + 1, r);

  // for(auto tmp : M[x]) {
  //     int type = tmp.first.first, x = tmp.first.second, t = tmp.second;
  //     if(type == OUT) {
  //         // printf("reverting x = %d t = %d\n", x, t);
  //         s[t][x]++;
  //     }
  // }

  // while(!changes.empty() and changes.back().first == x) {
  //     *changes.back().second.first = changes.back().second.second;
  //     changes.pop_back();
  // }
}

int x1[N], t1[N], a1[N], b1[N], x2[N], y2[N];

int main() {

  n = read();
  k = read();
  q = read();

  for (int i = 1; i <= n; i++) {
    int x, t, a, b;
    x = read();
    t = read();
    a = read();
    b = read();
    assert(a == 1);
    x1[i] = x, t1[i] = t, a1[i] = a, b1[i] = b;
  }

  for (int i = 1; i <= q; i++) {
    int x, y;
    x = read();
    y = read();
    x2[i] = x;
    y2[i] = y;
    ins.push_back(y);
    ques.push_back(x);
  }

  sort(ques.begin(), ques.end());
  ques.resize(unique(ques.begin(), ques.end()) - ques.begin());
  z = ques.size();

  ins.push_back(0);
  ins.push_back(1e8 + 1);

  sort(ins.begin(), ins.end());
  ins.resize(unique(ins.begin(), ins.end()) - ins.begin());
  g = ins.size();

  for (int i = 1; i <= n; i++) {
    int x = x1[i], t = t1[i], a = a1[i], b = b1[i];
    s[t][x]++;
    a = li(a - 1);
    b = ri(b + 1);
    if (a != 1) {
      create(1, OUT, 1, g, 1, a, x, t);
    }
    if (b != g) {
      create(1, OUT, 1, g, b, g, x, t);
    }
  }

  for (int i = 1; i <= q; i++) {
    int x = x2[i], y = y2[i];
    ans[i] = -1;
    create(1, QUE, 1, g, ri(y), ri(y), x, i);
  }

  memset(tree, -63, sizeof(tree));

  for (int i = 1; i <= k; i++) {
    vector<int> v;
    for (auto x : s[i])
      v.push_back(x.first);
    if (v.empty())
      break;
    total++;
    update(addNegative, 1, rid(v[0]), v[0]);
    for (int it = 0; it + 1 < v.size(); it++) {
      update(addPositive, rid(v[it]), lid((v[it] + v[it + 1]) / 2), -v[it]);
      update(addNegative, rid((v[it] + v[it + 1]) / 2 + 1), lid(v[it + 1]), v[it + 1]);
    }
    update(addPositive, rid(v.back()), z, -v.back());
  }

  changes.clear();

  if (total == k)
    solve(1, 1, g);

  for (int i = 1; i <= q; i++)
    printf("%d\n", ans[i]);

  return 0;
}

Compilation message

new_home.cpp: In function 'bool solve(int, int, int)':
new_home.cpp:98:7: warning: unused variable 'delTotal' [-Wunused-variable]
   98 |   int delTotal = 0;
      |       ^~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:248:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  248 |     for (int it = 0; it + 1 < v.size(); it++) {
      |                      ~~~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47200 KB Output is correct
2 Runtime error 57 ms 86172 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47200 KB Output is correct
2 Runtime error 57 ms 86172 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 141424 KB Output is correct
2 Correct 726 ms 116928 KB Output is correct
3 Correct 751 ms 116748 KB Output is correct
4 Correct 818 ms 141392 KB Output is correct
5 Correct 650 ms 99396 KB Output is correct
6 Correct 686 ms 117104 KB Output is correct
7 Correct 632 ms 116840 KB Output is correct
8 Correct 800 ms 141372 KB Output is correct
9 Correct 732 ms 141408 KB Output is correct
10 Correct 669 ms 141456 KB Output is correct
11 Correct 473 ms 141180 KB Output is correct
12 Correct 543 ms 141268 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 146164 KB Output is correct
2 Correct 134 ms 67184 KB Output is correct
3 Correct 1455 ms 141692 KB Output is correct
4 Correct 760 ms 129700 KB Output is correct
5 Correct 876 ms 154168 KB Output is correct
6 Correct 897 ms 154140 KB Output is correct
7 Correct 1411 ms 128384 KB Output is correct
8 Correct 1444 ms 153328 KB Output is correct
9 Correct 714 ms 130100 KB Output is correct
10 Correct 1084 ms 154244 KB Output is correct
11 Correct 1309 ms 154036 KB Output is correct
12 Correct 1301 ms 153392 KB Output is correct
13 Correct 652 ms 152044 KB Output is correct
14 Correct 634 ms 151796 KB Output is correct
15 Correct 760 ms 152536 KB Output is correct
16 Correct 883 ms 153144 KB Output is correct
17 Correct 787 ms 152292 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47200 KB Output is correct
2 Runtime error 57 ms 86172 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47200 KB Output is correct
2 Runtime error 57 ms 86172 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -