Submission #829638

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
829638	2023-08-18T13:42:28 Z	erdemkiraz	New Home (APIO18_new_home)	C++17	10 / 100	1531 ms	140780 KB

new_home

#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();
}

void 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) {
  //     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) {
    if (!HARD_FAIL) {
      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);
        }
      }
    }
  } else {
    int m = (l + r) >> 1;
    solve(x + x, l, m);
    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 'void 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:243:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  243 |     for (int it = 0; it + 1 < v.size(); it++) {
      |                      ~~~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	47316 KB	Output is correct
2	Runtime error	49 ms	86072 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	20 ms	47316 KB	Output is correct
2	Runtime error	49 ms	86072 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	840 ms	136156 KB	Output is correct
2	Correct	693 ms	111700 KB	Output is correct
3	Correct	738 ms	111612 KB	Output is correct
4	Correct	850 ms	136204 KB	Output is correct
5	Correct	681 ms	94204 KB	Output is correct
6	Correct	667 ms	111916 KB	Output is correct
7	Correct	644 ms	111568 KB	Output is correct
8	Correct	732 ms	136172 KB	Output is correct
9	Correct	754 ms	136204 KB	Output is correct
10	Correct	679 ms	136180 KB	Output is correct
11	Correct	527 ms	135860 KB	Output is correct
12	Correct	539 ms	136048 KB	Output is correct