oj.uz

Submission #881752

# Submission time Handle Problem Language Result Execution time Memory
881752 2023-12-01T20:19:46 Z MilosMilutinovic Segments (IZhO18_segments) C++14
7 / 100
 3545 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5;
const int M = 20 * N;

int root[N][2], ls[M], rs[M], cnt[M], tsz;

void Modify(int& x, int y, int l, int r, int p) {
  x = ++tsz;
  ls[x] = ls[y];
  rs[x] = rs[y];
  cnt[x] = cnt[y] + 1;
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid) {
    Modify(ls[x], ls[y], l, mid, p);
  } else {
    Modify(rs[x], rs[y], mid + 1, r, p);
  }
}

int Query(int x, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    return cnt[x];
  }
  int mid = l + r >> 1;
  if (rr <= mid) {
    return Query(ls[x], l, mid, ll, rr);
  } else if (ll > mid) {
    return Query(rs[x], mid + 1, r, ll, rr);
  } else {
    return Query(ls[x], l, mid, ll, rr) + Query(rs[x], mid + 1, r, ll, rr);
  }
}

void clear_seg() {
  while (tsz > 0) {
    ls[tsz] = 0;
    rs[tsz] = 0;
    cnt[tsz] = 0;
    tsz--;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, t;
  cin >> n >> t;
  vector<int> op(n), a(n), b(n), k(n);
  for (int i = 0; i < n; i++) {
    cin >> op[i];
    if (op[i] == 1) {
      cin >> a[i] >> b[i];
    }
    if (op[i] == 2) {
      cin >> a[i];
      --a[i];
    }
    if (op[i] == 3) {
      cin >> a[i] >> b[i] >> k[i];
    }
  }
  vector<int> vec;
  vector<int> idx(n);
  vector<int> to(n, n);
  for (int i = 0; i < n; i++) {
    if (op[i] == 1) {
      vec.push_back(i);
    }
    if (op[i] == 2) {
      idx[i] = vec[a[i]];
      to[idx[i]] = i;
    }
  }
  const int BLOCK = 1500;
  int res = 0;
  for (int L = 0; L < n; L += BLOCK) {
    int R = min(L + BLOCK, n);
    vector<int> xs;
    for (int i = 0; i < L; i++) {
      if (op[i] == 1) {
        if (to[i] >= R) {
          xs.push_back(a[i]);
          xs.push_back(b[i]);
          xs.push_back(b[i] - a[i] + 1);
        }
      }
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int sz = (int) xs.size();
    vector<vector<pair<int, int>>> qs(sz);
    for (int i = 0; i < L; i++) {
      if (op[i] == 1) {
        if (to[i] >= R) {
          int ll = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
          int rr = (int) (lower_bound(xs.begin(), xs.end(), b[i]) - xs.begin());
          int len = (int) (lower_bound(xs.begin(), xs.end(), b[i] - a[i] + 1) - xs.begin());
          qs[rr].push_back({ll, len});
        }
      }
    }
    xs.clear();
    clear_seg();
    for (int i = sz - 1; i >= 0; i--) {
      if (i + 1 < sz) {
        root[i][0] = root[i + 1][0];
        root[i][1] = root[i + 1][1];
      } else {
        root[i][0] = 0;
        root[i][1] = 0;
      }
      for (auto &p : qs[i]) {
        Modify(root[i][0], root[i][0], 0, sz - 1, p.first);
        Modify(root[i][1], root[i][1], 0, sz - 1, p.second);
      }
      qs[i].clear();
    }
    qs.clear();
    vector<int> cur;
    for (int i = 0; i < R; i++) {
      if (op[i] == 1 && (i >= L || (to[i] >= L && to[i] < R))) {
        cur.push_back(i);
      }
    }
    for (int i = L; i < R; i++) {
      if (op[i] == 1) {
        a[i] = (a[i] ^ (t * res));
        b[i] = (b[i] ^ (t * res));
        if (a[i] > b[i]) {
          swap(a[i], b[i]);
        }
      }
      if (op[i] == 3) {
        a[i] = (a[i] ^ (t * res));
        b[i] = (b[i] ^ (t * res));
        if (a[i] > b[i]) {
          swap(a[i], b[i]);
        }
        res = 0;
        if (b[i] - a[i] + 1 < k[i]) {
          cout << 0 << '\n';
          continue;
        }
        for (int j : cur) {
          if (j < i && op[j] == 1 && to[j] >= i) {
            int ll = max(a[i], a[j]);
            int rr = min(b[i], b[j]);
            if (rr - ll + 1 >= k[i]) {
              res += 1;
            }
          }
        }
        int idx = -1;
        {
          int low = 0, high = sz - 1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xs[mid] >= k[i]) {
              idx = mid;
              high = mid - 1;
            } else {
              low = mid + 1;
            }
          }
        }
        {
          int low = 0, high = sz - 1, pos = -1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xs[mid] >= a[i] + k[i] - 1) {
              pos = mid;
              high = mid - 1;
            } else {
              low = mid + 1;
            }
          }
          if (pos != -1 && idx != -1) {
            res += Query(root[pos][1], 0, sz - 1, idx, sz - 1);
          }
        }
        {
          int low = 0, high = sz - 1, posR = -1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xs[mid] > b[i]) {
              posR = mid;
              high = mid - 1;
            } else {
              low = mid + 1;
            }
          }
          low = 0, high = sz - 1;
          int posL = -1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xs[mid] <= b[i] - k[i] + 1) {
              posL = mid;
              low = mid + 1;
            } else {
              high = mid - 1;
            }
          }
          if (posR != -1 && posL != -1) {
            res += Query(root[posR][0], 0, sz - 1, 0, posL);
          }
          if (posR != -1 && idx != -1) {
            res -= Query(root[posR][1], 0, sz - 1, idx, sz - 1);
          }
        }
        cout << res << '\n';
      }
    }
    cur.clear();
  }
  return 0;
}

Compilation message

segments.cpp: In function 'void Modify(int&, int, int, int, int)':
segments.cpp:18:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |   int mid = l + r >> 1;
      |             ~~^~~
segments.cpp: In function 'int Query(int, int, int, int, int)':
segments.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int mid = l + r >> 1;
      |             ~~^~~
segments.cpp: In function 'int main()':
segments.cpp:163:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  163 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:175:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  175 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:190:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  190 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:201:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  201 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 11 ms 6280 KB Output is correct
6 Correct 12 ms 6024 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 11 ms 5808 KB Output is correct
9 Correct 11 ms 5820 KB Output is correct
10 Correct 8 ms 6280 KB Output is correct
11 Correct 11 ms 5724 KB Output is correct
12 Correct 10 ms 5724 KB Output is correct
13 Correct 8 ms 6280 KB Output is correct
14 Correct 10 ms 5832 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 2652 KB Output is correct
17 Correct 9 ms 3160 KB Output is correct
18 Correct 9 ms 6032 KB Output is correct
19 Correct 9 ms 3160 KB Output is correct
20 Correct 9 ms 3256 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2468 ms 37560 KB Output is correct
2 Correct 2501 ms 38028 KB Output is correct
3 Correct 2505 ms 38212 KB Output is correct
4 Runtime error 2696 ms 44112 KB Memory limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 5084 KB Output is correct
2 Correct 92 ms 5464 KB Output is correct
3 Correct 112 ms 5336 KB Output is correct
4 Correct 97 ms 5244 KB Output is correct
5 Runtime error 1535 ms 65536 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 5088 KB Output is correct
2 Correct 93 ms 5256 KB Output is correct
3 Correct 94 ms 5176 KB Output is correct
4 Correct 101 ms 5336 KB Output is correct
5 Runtime error 3545 ms 65536 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 11 ms 6280 KB Output is correct
6 Correct 12 ms 6024 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 11 ms 5808 KB Output is correct
9 Correct 11 ms 5820 KB Output is correct
10 Correct 8 ms 6280 KB Output is correct
11 Correct 11 ms 5724 KB Output is correct
12 Correct 10 ms 5724 KB Output is correct
13 Correct 8 ms 6280 KB Output is correct
14 Correct 10 ms 5832 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 2652 KB Output is correct
17 Correct 9 ms 3160 KB Output is correct
18 Correct 9 ms 6032 KB Output is correct
19 Correct 9 ms 3160 KB Output is correct
20 Correct 9 ms 3256 KB Output is correct
21 Correct 2468 ms 37560 KB Output is correct
22 Correct 2501 ms 38028 KB Output is correct
23 Correct 2505 ms 38212 KB Output is correct
24 Runtime error 2696 ms 44112 KB Memory limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 11 ms 6280 KB Output is correct
6 Correct 12 ms 6024 KB Output is correct
7 Correct 8 ms 2836 KB Output is correct
8 Correct 11 ms 5808 KB Output is correct
9 Correct 11 ms 5820 KB Output is correct
10 Correct 8 ms 6280 KB Output is correct
11 Correct 11 ms 5724 KB Output is correct
12 Correct 10 ms 5724 KB Output is correct
13 Correct 8 ms 6280 KB Output is correct
14 Correct 10 ms 5832 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 2652 KB Output is correct
17 Correct 9 ms 3160 KB Output is correct
18 Correct 9 ms 6032 KB Output is correct
19 Correct 9 ms 3160 KB Output is correct
20 Correct 9 ms 3256 KB Output is correct
21 Correct 2468 ms 37560 KB Output is correct
22 Correct 2501 ms 38028 KB Output is correct
23 Correct 2505 ms 38212 KB Output is correct
24 Runtime error 2696 ms 44112 KB Memory limit exceeded
25 Halted 0 ms 0 KB -