oj.uz

Submission #881770

# Submission time Handle Problem Language Result Execution time Memory
881770 2023-12-01T21:21:29 Z MilosMilutinovic Segments (IZhO18_segments) C++14
7 / 100
 5000 ms 59700 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 = 1000;
  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;
}

/*
6 1
1 1 2
3 2 4 2
1 3 5
3 2 3 1
2 1
3 0 3 1


6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2
*/

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 2908 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 10 ms 6136 KB Output is correct
6 Correct 10 ms 5980 KB Output is correct
7 Correct 7 ms 2968 KB Output is correct
8 Correct 10 ms 5720 KB Output is correct
9 Correct 10 ms 5724 KB Output is correct
10 Correct 9 ms 5988 KB Output is correct
11 Correct 10 ms 5724 KB Output is correct
12 Correct 11 ms 5720 KB Output is correct
13 Correct 10 ms 5976 KB Output is correct
14 Correct 10 ms 5724 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 3 ms 2908 KB Output is correct
17 Correct 8 ms 3268 KB Output is correct
18 Correct 9 ms 5980 KB Output is correct
19 Correct 9 ms 3164 KB Output is correct
20 Correct 9 ms 3420 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3833 ms 37504 KB Output is correct
2 Correct 3769 ms 37456 KB Output is correct
3 Correct 3788 ms 37492 KB Output is correct
4 Correct 4099 ms 39824 KB Output is correct
5 Execution timed out 5016 ms 59700 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 10436 KB Output is correct
2 Correct 115 ms 9952 KB Output is correct
3 Correct 137 ms 10036 KB Output is correct
4 Correct 118 ms 10120 KB Output is correct
5 Runtime error 4728 ms 47940 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9948 KB Output is correct
2 Correct 130 ms 10112 KB Output is correct
3 Correct 125 ms 9948 KB Output is correct
4 Correct 123 ms 10208 KB Output is correct
5 Execution timed out 5033 ms 49924 KB Time 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 2908 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 10 ms 6136 KB Output is correct
6 Correct 10 ms 5980 KB Output is correct
7 Correct 7 ms 2968 KB Output is correct
8 Correct 10 ms 5720 KB Output is correct
9 Correct 10 ms 5724 KB Output is correct
10 Correct 9 ms 5988 KB Output is correct
11 Correct 10 ms 5724 KB Output is correct
12 Correct 11 ms 5720 KB Output is correct
13 Correct 10 ms 5976 KB Output is correct
14 Correct 10 ms 5724 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 3 ms 2908 KB Output is correct
17 Correct 8 ms 3268 KB Output is correct
18 Correct 9 ms 5980 KB Output is correct
19 Correct 9 ms 3164 KB Output is correct
20 Correct 9 ms 3420 KB Output is correct
21 Correct 3833 ms 37504 KB Output is correct
22 Correct 3769 ms 37456 KB Output is correct
23 Correct 3788 ms 37492 KB Output is correct
24 Correct 4099 ms 39824 KB Output is correct
25 Execution timed out 5016 ms 59700 KB Time limit exceeded
26 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 2908 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 10 ms 6136 KB Output is correct
6 Correct 10 ms 5980 KB Output is correct
7 Correct 7 ms 2968 KB Output is correct
8 Correct 10 ms 5720 KB Output is correct
9 Correct 10 ms 5724 KB Output is correct
10 Correct 9 ms 5988 KB Output is correct
11 Correct 10 ms 5724 KB Output is correct
12 Correct 11 ms 5720 KB Output is correct
13 Correct 10 ms 5976 KB Output is correct
14 Correct 10 ms 5724 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 3 ms 2908 KB Output is correct
17 Correct 8 ms 3268 KB Output is correct
18 Correct 9 ms 5980 KB Output is correct
19 Correct 9 ms 3164 KB Output is correct
20 Correct 9 ms 3420 KB Output is correct
21 Correct 3833 ms 37504 KB Output is correct
22 Correct 3769 ms 37456 KB Output is correct
23 Correct 3788 ms 37492 KB Output is correct
24 Correct 4099 ms 39824 KB Output is correct
25 Execution timed out 5016 ms 59700 KB Time limit exceeded
26 Halted 0 ms 0 KB -