oj.uz

Submission #683595

# Submission time Handle Problem Language Result Execution time Memory
683595 2023-01-18T20:16:08 Z acm Segments (IZhO18_segments) C++17
59 / 100
 5000 ms 6132 KB 
#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define precision     \
  cout.precision(30); \
  cerr.precision(10);
#define ll long long
#define ld long double
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define F first
#define S second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void ioi(string name) {
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}
const int bl = 900;
int n, m, g, t, sz, lastans, a[2][200005], b[2][200005], c[2][200005],
    pos[200005];
pair<int, int> d[bl + 5], e[200005];
inline int kek(int l, int r, int x) {
  int new_ans = 0;
#pragma GCC ivdep
  for (int i = 1; i <= sz; i++)
    new_ans +=
        c[0][d[i].S] <= r - x + 1 && c[1][d[i].S] >= l + x - 1 && x <= d[i].F;
  int p = lower_bound(e + 1, e + m + 1, mp(x, 0)) - e;
  p = m - p + 1;
  for (int i = 1; i <= p; i++)
    new_ans += b[0][i] <= r - x + 1 && b[1][i] >= l + x - 1;
  return new_ans;
}
void mrg() {
  pair<int, int> tmp[sz + m + 5];
  merge(e + 1, e + m + 1, d + 1, d + sz + 1, tmp + 1);
  m += sz;
  sz = 0;
  for (int i = 1; i <= m; i++) e[i] = tmp[i];
}
void bld() {
  sort(d + 1, d + sz + 1);
  mrg();
  for (int i = 1; i <= m; i++)
    b[0][m - i + 1] = c[0][e[i].S], b[1][m - i + 1] = c[1][e[i].S],
                 pos[e[i].S] = m - i + 1;
}
int main() {
  speed;
  precision;
  // code
  cin >> n >> t;
  for (int i = 1; i <= n; i++) {
    int type, l, r, x;
    cin >> type;
    if (type == 1) {
      cin >> l >> r;
      l ^= t * lastans;
      r ^= t * lastans;
      if (l > r) swap(l, r);
      ++g;
      c[0][g] = l;
      c[1][g] = r;
      d[++sz] = mp(r - l + 1, g);
    }
    if (type == 2) {
      cin >> x;
      c[0][x] = 1e9;
      c[1][x] = -1e9;
      b[0][pos[x]] = 1e9;
      b[1][pos[x]] = -1e9;
    }
    if (type == 3) {
      cin >> l >> r >> x;
      l ^= t * lastans;
      r ^= t * lastans;
      if (l > r) swap(l, r);
      cout << (lastans = kek(l, r, x)) << "\n";
    }
    if (bl <= sz) bld();
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Compilation message

segments.cpp: In function 'void ioi(std::string)':
segments.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 11 ms 596 KB Output is correct
6 Correct 10 ms 588 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 7 ms 468 KB Output is correct
9 Correct 8 ms 468 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 16 ms 560 KB Output is correct
12 Correct 17 ms 468 KB Output is correct
13 Correct 5 ms 592 KB Output is correct
14 Correct 8 ms 452 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 8 ms 468 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 8 ms 472 KB Output is correct
20 Correct 9 ms 532 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3445 ms 5236 KB Output is correct
2 Correct 3363 ms 5048 KB Output is correct
3 Correct 3434 ms 5128 KB Output is correct
4 Correct 3280 ms 5296 KB Output is correct
5 Correct 764 ms 5956 KB Output is correct
6 Correct 435 ms 6132 KB Output is correct
7 Correct 3458 ms 5056 KB Output is correct
8 Correct 3419 ms 5256 KB Output is correct
9 Correct 3400 ms 5180 KB Output is correct
10 Correct 2242 ms 4328 KB Output is correct
11 Correct 2674 ms 4584 KB Output is correct
12 Correct 2760 ms 5480 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 3428 KB Output is correct
2 Correct 463 ms 3388 KB Output is correct
3 Correct 530 ms 3480 KB Output is correct
4 Correct 420 ms 3424 KB Output is correct
5 Correct 4107 ms 5520 KB Output is correct
6 Correct 4733 ms 5200 KB Output is correct
7 Correct 4534 ms 5236 KB Output is correct
8 Correct 1091 ms 5936 KB Output is correct
9 Correct 702 ms 5800 KB Output is correct
10 Correct 1961 ms 5296 KB Output is correct
11 Correct 1085 ms 3548 KB Output is correct
12 Correct 1895 ms 5316 KB Output is correct
13 Correct 1770 ms 4972 KB Output is correct
14 Correct 2970 ms 4396 KB Output is correct
15 Correct 3075 ms 4176 KB Output is correct
16 Correct 2884 ms 3928 KB Output is correct
17 Execution timed out 5028 ms 4712 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 3584 KB Output is correct
2 Correct 307 ms 3608 KB Output is correct
3 Correct 306 ms 3572 KB Output is correct
4 Correct 313 ms 3552 KB Output is correct
5 Correct 2348 ms 5652 KB Output is correct
6 Correct 1615 ms 4416 KB Output is correct
7 Correct 1806 ms 5828 KB Output is correct
8 Correct 2331 ms 4500 KB Output is correct
9 Correct 1985 ms 4644 KB Output is correct
10 Correct 1197 ms 5472 KB Output is correct
11 Correct 1601 ms 4056 KB Output is correct
12 Correct 267 ms 5964 KB Output is correct
13 Correct 1630 ms 5160 KB Output is correct
14 Correct 2515 ms 4476 KB Output is correct
15 Correct 478 ms 5984 KB Output is correct
16 Correct 1451 ms 5244 KB Output is correct
17 Correct 3249 ms 5344 KB Output is correct
18 Correct 3265 ms 5088 KB Output is correct
19 Correct 3303 ms 5124 KB Output is correct
20 Correct 3279 ms 5364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 11 ms 596 KB Output is correct
6 Correct 10 ms 588 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 7 ms 468 KB Output is correct
9 Correct 8 ms 468 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 16 ms 560 KB Output is correct
12 Correct 17 ms 468 KB Output is correct
13 Correct 5 ms 592 KB Output is correct
14 Correct 8 ms 452 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 8 ms 468 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 8 ms 472 KB Output is correct
20 Correct 9 ms 532 KB Output is correct
21 Correct 3445 ms 5236 KB Output is correct
22 Correct 3363 ms 5048 KB Output is correct
23 Correct 3434 ms 5128 KB Output is correct
24 Correct 3280 ms 5296 KB Output is correct
25 Correct 764 ms 5956 KB Output is correct
26 Correct 435 ms 6132 KB Output is correct
27 Correct 3458 ms 5056 KB Output is correct
28 Correct 3419 ms 5256 KB Output is correct
29 Correct 3400 ms 5180 KB Output is correct
30 Correct 2242 ms 4328 KB Output is correct
31 Correct 2674 ms 4584 KB Output is correct
32 Correct 2760 ms 5480 KB Output is correct
33 Correct 300 ms 3584 KB Output is correct
34 Correct 307 ms 3608 KB Output is correct
35 Correct 306 ms 3572 KB Output is correct
36 Correct 313 ms 3552 KB Output is correct
37 Correct 2348 ms 5652 KB Output is correct
38 Correct 1615 ms 4416 KB Output is correct
39 Correct 1806 ms 5828 KB Output is correct
40 Correct 2331 ms 4500 KB Output is correct
41 Correct 1985 ms 4644 KB Output is correct
42 Correct 1197 ms 5472 KB Output is correct
43 Correct 1601 ms 4056 KB Output is correct
44 Correct 267 ms 5964 KB Output is correct
45 Correct 1630 ms 5160 KB Output is correct
46 Correct 2515 ms 4476 KB Output is correct
47 Correct 478 ms 5984 KB Output is correct
48 Correct 1451 ms 5244 KB Output is correct
49 Correct 3249 ms 5344 KB Output is correct
50 Correct 3265 ms 5088 KB Output is correct
51 Correct 3303 ms 5124 KB Output is correct
52 Correct 3279 ms 5364 KB Output is correct
53 Correct 337 ms 3660 KB Output is correct
54 Correct 324 ms 3716 KB Output is correct
55 Correct 308 ms 3580 KB Output is correct
56 Correct 318 ms 3596 KB Output is correct
57 Correct 3132 ms 4864 KB Output is correct
58 Correct 1120 ms 4144 KB Output is correct
59 Correct 3098 ms 5440 KB Output is correct
60 Correct 965 ms 4052 KB Output is correct
61 Correct 1539 ms 5200 KB Output is correct
62 Correct 635 ms 5928 KB Output is correct
63 Correct 364 ms 5904 KB Output is correct
64 Correct 589 ms 5696 KB Output is correct
65 Correct 2553 ms 4272 KB Output is correct
66 Correct 2397 ms 4192 KB Output is correct
67 Correct 1422 ms 5308 KB Output is correct
68 Correct 1990 ms 4900 KB Output is correct
69 Correct 3312 ms 5200 KB Output is correct
70 Correct 3282 ms 5056 KB Output is correct
71 Correct 3297 ms 5048 KB Output is correct
72 Correct 3284 ms 5172 KB Output is correct
73 Correct 2029 ms 4256 KB Output is correct
74 Correct 1792 ms 4944 KB Output is correct
75 Correct 151 ms 6016 KB Output is correct
76 Correct 368 ms 5996 KB Output is correct
77 Correct 313 ms 3664 KB Output is correct
78 Correct 311 ms 3640 KB Output is correct
79 Correct 316 ms 3624 KB Output is correct
80 Correct 310 ms 3636 KB Output is correct
81 Correct 1897 ms 4812 KB Output is correct
82 Correct 2070 ms 4276 KB Output is correct
83 Correct 1555 ms 3956 KB Output is correct
84 Correct 1831 ms 4944 KB Output is correct
85 Correct 1422 ms 5104 KB Output is correct
86 Correct 1315 ms 5324 KB Output is correct
87 Correct 2493 ms 4436 KB Output is correct
88 Correct 2293 ms 4068 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 11 ms 596 KB Output is correct
6 Correct 10 ms 588 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 7 ms 468 KB Output is correct
9 Correct 8 ms 468 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 16 ms 560 KB Output is correct
12 Correct 17 ms 468 KB Output is correct
13 Correct 5 ms 592 KB Output is correct
14 Correct 8 ms 452 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 8 ms 468 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 8 ms 472 KB Output is correct
20 Correct 9 ms 532 KB Output is correct
21 Correct 3445 ms 5236 KB Output is correct
22 Correct 3363 ms 5048 KB Output is correct
23 Correct 3434 ms 5128 KB Output is correct
24 Correct 3280 ms 5296 KB Output is correct
25 Correct 764 ms 5956 KB Output is correct
26 Correct 435 ms 6132 KB Output is correct
27 Correct 3458 ms 5056 KB Output is correct
28 Correct 3419 ms 5256 KB Output is correct
29 Correct 3400 ms 5180 KB Output is correct
30 Correct 2242 ms 4328 KB Output is correct
31 Correct 2674 ms 4584 KB Output is correct
32 Correct 2760 ms 5480 KB Output is correct
33 Correct 451 ms 3428 KB Output is correct
34 Correct 463 ms 3388 KB Output is correct
35 Correct 530 ms 3480 KB Output is correct
36 Correct 420 ms 3424 KB Output is correct
37 Correct 4107 ms 5520 KB Output is correct
38 Correct 4733 ms 5200 KB Output is correct
39 Correct 4534 ms 5236 KB Output is correct
40 Correct 1091 ms 5936 KB Output is correct
41 Correct 702 ms 5800 KB Output is correct
42 Correct 1961 ms 5296 KB Output is correct
43 Correct 1085 ms 3548 KB Output is correct
44 Correct 1895 ms 5316 KB Output is correct
45 Correct 1770 ms 4972 KB Output is correct
46 Correct 2970 ms 4396 KB Output is correct
47 Correct 3075 ms 4176 KB Output is correct
48 Correct 2884 ms 3928 KB Output is correct
49 Execution timed out 5028 ms 4712 KB Time limit exceeded
50 Halted 0 ms 0 KB -