oj.uz

Submission #881759

# Submission time Handle Problem Language Result Execution time Memory
881759 2023-12-01T20:28:57 Z MilosMilutinovic Segments (IZhO18_segments) C++14
7 / 100
 350 ms 62984 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
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 = 1600;
  int res = 0;
  vector<vector<pair<int, int>>> qs(3 * n);
  vector<int> xs;
  vector<int> cur;
  for (int L = 0; L < n; L += BLOCK) {
    int R = min(L + BLOCK, n);
    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();
    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();
    }
    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:162:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  162 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:174:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  174 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:189:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  189 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:200:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  200 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 12 ms 4452 KB Output is correct
6 Correct 13 ms 4196 KB Output is correct
7 Correct 8 ms 1116 KB Output is correct
8 Correct 10 ms 4028 KB Output is correct
9 Correct 10 ms 3932 KB Output is correct
10 Correct 9 ms 4444 KB Output is correct
11 Correct 13 ms 3916 KB Output is correct
12 Correct 12 ms 3932 KB Output is correct
13 Correct 9 ms 4444 KB Output is correct
14 Correct 10 ms 3932 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 3 ms 988 KB Output is correct
17 Correct 9 ms 1372 KB Output is correct
18 Correct 9 ms 4380 KB Output is correct
19 Correct 9 ms 1368 KB Output is correct
20 Correct 9 ms 1372 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 10240 KB Output is correct
2 Correct 93 ms 10240 KB Output is correct
3 Correct 106 ms 10204 KB Output is correct
4 Correct 103 ms 10208 KB Output is correct
5 Runtime error 332 ms 62824 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 10244 KB Output is correct
2 Correct 94 ms 10176 KB Output is correct
3 Correct 98 ms 10116 KB Output is correct
4 Correct 101 ms 10196 KB Output is correct
5 Runtime error 331 ms 62984 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 12 ms 4452 KB Output is correct
6 Correct 13 ms 4196 KB Output is correct
7 Correct 8 ms 1116 KB Output is correct
8 Correct 10 ms 4028 KB Output is correct
9 Correct 10 ms 3932 KB Output is correct
10 Correct 9 ms 4444 KB Output is correct
11 Correct 13 ms 3916 KB Output is correct
12 Correct 12 ms 3932 KB Output is correct
13 Correct 9 ms 4444 KB Output is correct
14 Correct 10 ms 3932 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 3 ms 988 KB Output is correct
17 Correct 9 ms 1372 KB Output is correct
18 Correct 9 ms 4380 KB Output is correct
19 Correct 9 ms 1368 KB Output is correct
20 Correct 9 ms 1372 KB Output is correct
21 Runtime error 350 ms 61212 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 12 ms 4452 KB Output is correct
6 Correct 13 ms 4196 KB Output is correct
7 Correct 8 ms 1116 KB Output is correct
8 Correct 10 ms 4028 KB Output is correct
9 Correct 10 ms 3932 KB Output is correct
10 Correct 9 ms 4444 KB Output is correct
11 Correct 13 ms 3916 KB Output is correct
12 Correct 12 ms 3932 KB Output is correct
13 Correct 9 ms 4444 KB Output is correct
14 Correct 10 ms 3932 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 3 ms 988 KB Output is correct
17 Correct 9 ms 1372 KB Output is correct
18 Correct 9 ms 4380 KB Output is correct
19 Correct 9 ms 1368 KB Output is correct
20 Correct 9 ms 1372 KB Output is correct
21 Runtime error 350 ms 61212 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -