oj.uz

Submission #881764

# Submission time Handle Problem Language Result Execution time Memory
881764 2023-12-01T20:59:10 Z MilosMilutinovic Segments (IZhO18_segments) C++14
7 / 100
 3704 ms 64308 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 = 1600;
  int res = 0;
  vector<vector<vector<int>>> qs(2, vector<vector<int>>(2 * n));
  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) {
          xsL.push_back(a[i]);
          xsL.push_back(b[i]);
          xsR.push_back(b[i]);
          xsR.push_back(b[i] - a[i] + 1);
        }
      }
    }
    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 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(xsL.begin(), xsL.end(), b[i]) - xsL.begin());
            qs[0][rr].push_back(ll);
          }
          {            
            int rr = (int) (lower_bound(xsR.begin(), xsR.end(), b[i]) - xsR.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 = szL - 1; i >= 0; i--) {
      if (i + 1 < szL) {
        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 = szR - 1; i >= 0; i--) {
      if (i + 1 < szR) {
        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 = szR - 1, pos = -1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xsR[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 = szR - 1, pos = -1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xsR[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 = szL - 1, posR = -1;
          while (low <= high) {
            int mid = low + high >> 1;
            if (xsL[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:182:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  182 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:194:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  194 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:209:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  209 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:224:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  224 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~
segments.cpp:235:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  235 |             int mid = low + high >> 1;
      |                       ~~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 1244 KB Output is correct
4 Correct 4 ms 3184 KB Output is correct
5 Correct 14 ms 6768 KB Output is correct
6 Correct 14 ms 6544 KB Output is correct
7 Correct 9 ms 3436 KB Output is correct
8 Correct 14 ms 6256 KB Output is correct
9 Correct 14 ms 6252 KB Output is correct
10 Correct 12 ms 6768 KB Output is correct
11 Correct 13 ms 6256 KB Output is correct
12 Correct 13 ms 6256 KB Output is correct
13 Correct 11 ms 6868 KB Output is correct
14 Correct 13 ms 6000 KB Output is correct
15 Correct 3 ms 1248 KB Output is correct
16 Correct 4 ms 3180 KB Output is correct
17 Correct 11 ms 3696 KB Output is correct
18 Correct 11 ms 6572 KB Output is correct
19 Correct 10 ms 3696 KB Output is correct
20 Correct 10 ms 3744 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2805 ms 48244 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 18912 KB Output is correct
2 Correct 99 ms 18800 KB Output is correct
3 Correct 116 ms 18872 KB Output is correct
4 Correct 98 ms 18980 KB Output is correct
5 Runtime error 3512 ms 61632 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 19156 KB Output is correct
2 Correct 111 ms 19156 KB Output is correct
3 Correct 101 ms 19160 KB Output is correct
4 Correct 112 ms 19160 KB Output is correct
5 Runtime error 3704 ms 64308 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 1244 KB Output is correct
4 Correct 4 ms 3184 KB Output is correct
5 Correct 14 ms 6768 KB Output is correct
6 Correct 14 ms 6544 KB Output is correct
7 Correct 9 ms 3436 KB Output is correct
8 Correct 14 ms 6256 KB Output is correct
9 Correct 14 ms 6252 KB Output is correct
10 Correct 12 ms 6768 KB Output is correct
11 Correct 13 ms 6256 KB Output is correct
12 Correct 13 ms 6256 KB Output is correct
13 Correct 11 ms 6868 KB Output is correct
14 Correct 13 ms 6000 KB Output is correct
15 Correct 3 ms 1248 KB Output is correct
16 Correct 4 ms 3180 KB Output is correct
17 Correct 11 ms 3696 KB Output is correct
18 Correct 11 ms 6572 KB Output is correct
19 Correct 10 ms 3696 KB Output is correct
20 Correct 10 ms 3744 KB Output is correct
21 Runtime error 2805 ms 48244 KB Memory limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 1244 KB Output is correct
4 Correct 4 ms 3184 KB Output is correct
5 Correct 14 ms 6768 KB Output is correct
6 Correct 14 ms 6544 KB Output is correct
7 Correct 9 ms 3436 KB Output is correct
8 Correct 14 ms 6256 KB Output is correct
9 Correct 14 ms 6252 KB Output is correct
10 Correct 12 ms 6768 KB Output is correct
11 Correct 13 ms 6256 KB Output is correct
12 Correct 13 ms 6256 KB Output is correct
13 Correct 11 ms 6868 KB Output is correct
14 Correct 13 ms 6000 KB Output is correct
15 Correct 3 ms 1248 KB Output is correct
16 Correct 4 ms 3180 KB Output is correct
17 Correct 11 ms 3696 KB Output is correct
18 Correct 11 ms 6572 KB Output is correct
19 Correct 10 ms 3696 KB Output is correct
20 Correct 10 ms 3744 KB Output is correct
21 Runtime error 2805 ms 48244 KB Memory limit exceeded
22 Halted 0 ms 0 KB -