oj.uz

Submission #881768

# Submission time Handle Problem Language Result Execution time Memory
881768 2023-12-01T21:19:58 Z MilosMilutinovic Segments (IZhO18_segments) C++14
7 / 100
 1734 ms 50176 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 = 3000;
  int res = 0;
  vector<vector<vector<int>>> qs(2, vector<vector<int>>(n));
  vector<int> xs;
  vector<int> xsL;
  vector<int> xsR;
  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(b[i]);
          xsL.push_back(a[i]);
          xsR.push_back(b[i] - a[i] + 1);
        }
      }
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(xsL.begin(), xsL.end());
    xsL.erase(unique(xsL.begin(), xsL.end()), xsL.end());
    sort(xsR.begin(), xsR.end());
    xsR.erase(unique(xsR.begin(), xsR.end()), xsR.end());
    int sz = (int) xs.size();
    int szL = (int) xsL.size();
    int szR = (int) xsR.size();
    for (int i = 0; i < L; i++) {
      if (op[i] == 1) {
        if (to[i] >= R) {
          {
            int ll = (int) (lower_bound(xsL.begin(), xsL.end(), a[i]) - xsL.begin());
            int rr = (int) (lower_bound(xs.begin(), xs.end(), b[i]) - xs.begin());
            qs[0][rr].push_back(ll);
          }
          {            
            int rr = (int) (lower_bound(xs.begin(), xs.end(), b[i]) - xs.begin());
            int len = (int) (lower_bound(xsR.begin(), xsR.end(), b[i] - a[i] + 1) - xsR.begin());
            qs[1][rr].push_back(len);
          }
        }
      }
    }
    xsL.clear();
    xsR.clear();
    clear_seg();
    for (int i = sz - 1; i >= 0; i--) {
      if (i + 1 < sz) {
        root[i][0] = root[i + 1][0];
      } else {
        root[i][0] = 0;
      }
      for (auto &p : qs[0][i]) {
        Modify(root[i][0], root[i][0], 0, szL - 1, p);
      }
      qs[0][i].clear();
    }
    for (int i = sz - 1; i >= 0; i--) {
      if (i + 1 < sz) {
        root[i][1] = root[i + 1][1];
      } else {
        root[i][1] = 0;
      }
      for (auto &p : qs[1][i]) {
        Modify(root[i][1], root[i][1], 0, szR - 1, p);
      }
      qs[1][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 = szR - 1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xsR[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, szR - 1, idx, szR - 1);
          }
        }
        {
          int low = 0, high = sz - 1, pos = -1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xs[mid] > b[i]) {
              pos = mid;
              high = mid - 1;
            } else {
              low = mid + 1;
            }
          }
          if (pos != -1 && idx != -1) {
            res -= Query(root[pos][1], 0, szR - 1, idx, szR - 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 = szL - 1;
          int posL = -1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xsL[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, szL - 1, 0, posL);
          }
        }
        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:185:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  185 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:197:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  197 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:212:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  212 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:227:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  227 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:238:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  238 |             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 856 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 11 ms 5972 KB Output is correct
6 Correct 11 ms 5980 KB Output is correct
7 Correct 11 ms 2908 KB Output is correct
8 Correct 9 ms 5720 KB Output is correct
9 Correct 10 ms 5972 KB Output is correct
10 Correct 6 ms 5724 KB Output is correct
11 Correct 13 ms 5724 KB Output is correct
12 Correct 13 ms 5808 KB Output is correct
13 Correct 7 ms 5724 KB Output is correct
14 Correct 11 ms 5640 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 4 ms 2908 KB Output is correct
17 Correct 13 ms 3164 KB Output is correct
18 Correct 8 ms 5908 KB Output is correct
19 Correct 12 ms 3164 KB Output is correct
20 Correct 13 ms 3164 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1406 ms 37436 KB Output is correct
2 Correct 1364 ms 40268 KB Output is correct
3 Correct 1377 ms 39908 KB Output is correct
4 Runtime error 1456 ms 42688 KB Memory limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 9948 KB Output is correct
2 Correct 89 ms 9956 KB Output is correct
3 Correct 105 ms 10064 KB Output is correct
4 Correct 92 ms 10196 KB Output is correct
5 Runtime error 1652 ms 47748 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 9940 KB Output is correct
2 Correct 97 ms 10148 KB Output is correct
3 Correct 93 ms 9940 KB Output is correct
4 Correct 95 ms 10116 KB Output is correct
5 Runtime error 1734 ms 50176 KB Memory limit exceeded
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 856 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 11 ms 5972 KB Output is correct
6 Correct 11 ms 5980 KB Output is correct
7 Correct 11 ms 2908 KB Output is correct
8 Correct 9 ms 5720 KB Output is correct
9 Correct 10 ms 5972 KB Output is correct
10 Correct 6 ms 5724 KB Output is correct
11 Correct 13 ms 5724 KB Output is correct
12 Correct 13 ms 5808 KB Output is correct
13 Correct 7 ms 5724 KB Output is correct
14 Correct 11 ms 5640 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 4 ms 2908 KB Output is correct
17 Correct 13 ms 3164 KB Output is correct
18 Correct 8 ms 5908 KB Output is correct
19 Correct 12 ms 3164 KB Output is correct
20 Correct 13 ms 3164 KB Output is correct
21 Correct 1406 ms 37436 KB Output is correct
22 Correct 1364 ms 40268 KB Output is correct
23 Correct 1377 ms 39908 KB Output is correct
24 Runtime error 1456 ms 42688 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 856 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 11 ms 5972 KB Output is correct
6 Correct 11 ms 5980 KB Output is correct
7 Correct 11 ms 2908 KB Output is correct
8 Correct 9 ms 5720 KB Output is correct
9 Correct 10 ms 5972 KB Output is correct
10 Correct 6 ms 5724 KB Output is correct
11 Correct 13 ms 5724 KB Output is correct
12 Correct 13 ms 5808 KB Output is correct
13 Correct 7 ms 5724 KB Output is correct
14 Correct 11 ms 5640 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 4 ms 2908 KB Output is correct
17 Correct 13 ms 3164 KB Output is correct
18 Correct 8 ms 5908 KB Output is correct
19 Correct 12 ms 3164 KB Output is correct
20 Correct 13 ms 3164 KB Output is correct
21 Correct 1406 ms 37436 KB Output is correct
22 Correct 1364 ms 40268 KB Output is correct
23 Correct 1377 ms 39908 KB Output is correct
24 Runtime error 1456 ms 42688 KB Memory limit exceeded
25 Halted 0 ms 0 KB -