oj.uz

답안 #881751

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881751 2023-12-01T20:18:59 Z MilosMilutinovic Segments (IZhO18_segments) C++14
7 / 100
 3826 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 = 1400;
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 8 ms 6292 KB Output is correct
6 Correct 10 ms 6088 KB Output is correct
7 Correct 7 ms 2648 KB Output is correct
8 Correct 9 ms 5748 KB Output is correct
9 Correct 9 ms 5564 KB Output is correct
10 Correct 8 ms 6292 KB Output is correct
11 Correct 9 ms 5724 KB Output is correct
12 Correct 10 ms 5980 KB Output is correct
13 Correct 8 ms 6292 KB Output is correct
14 Correct 9 ms 5652 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 4 ms 2652 KB Output is correct
17 Correct 9 ms 3180 KB Output is correct
18 Correct 8 ms 6040 KB Output is correct
19 Correct 8 ms 3120 KB Output is correct
20 Correct 8 ms 3164 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2629 ms 38172 KB Output is correct
2 Correct 2676 ms 38228 KB Output is correct
3 Correct 2611 ms 37920 KB Output is correct
4 Runtime error 2845 ms 43616 KB Memory limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 5332 KB Output is correct
2 Correct 93 ms 5080 KB Output is correct
3 Correct 113 ms 5336 KB Output is correct
4 Correct 98 ms 5504 KB Output is correct
5 Runtime error 3807 ms 65536 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 5080 KB Output is correct
2 Correct 96 ms 5260 KB Output is correct
3 Correct 98 ms 5084 KB Output is correct
4 Correct 102 ms 5088 KB Output is correct
5 Runtime error 3826 ms 65536 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 8 ms 6292 KB Output is correct
6 Correct 10 ms 6088 KB Output is correct
7 Correct 7 ms 2648 KB Output is correct
8 Correct 9 ms 5748 KB Output is correct
9 Correct 9 ms 5564 KB Output is correct
10 Correct 8 ms 6292 KB Output is correct
11 Correct 9 ms 5724 KB Output is correct
12 Correct 10 ms 5980 KB Output is correct
13 Correct 8 ms 6292 KB Output is correct
14 Correct 9 ms 5652 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 4 ms 2652 KB Output is correct
17 Correct 9 ms 3180 KB Output is correct
18 Correct 8 ms 6040 KB Output is correct
19 Correct 8 ms 3120 KB Output is correct
20 Correct 8 ms 3164 KB Output is correct
21 Correct 2629 ms 38172 KB Output is correct
22 Correct 2676 ms 38228 KB Output is correct
23 Correct 2611 ms 37920 KB Output is correct
24 Runtime error 2845 ms 43616 KB Memory limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 8 ms 6292 KB Output is correct
6 Correct 10 ms 6088 KB Output is correct
7 Correct 7 ms 2648 KB Output is correct
8 Correct 9 ms 5748 KB Output is correct
9 Correct 9 ms 5564 KB Output is correct
10 Correct 8 ms 6292 KB Output is correct
11 Correct 9 ms 5724 KB Output is correct
12 Correct 10 ms 5980 KB Output is correct
13 Correct 8 ms 6292 KB Output is correct
14 Correct 9 ms 5652 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 4 ms 2652 KB Output is correct
17 Correct 9 ms 3180 KB Output is correct
18 Correct 8 ms 6040 KB Output is correct
19 Correct 8 ms 3120 KB Output is correct
20 Correct 8 ms 3164 KB Output is correct
21 Correct 2629 ms 38172 KB Output is correct
22 Correct 2676 ms 38228 KB Output is correct
23 Correct 2611 ms 37920 KB Output is correct
24 Runtime error 2845 ms 43616 KB Memory limit exceeded
25 Halted 0 ms 0 KB -