oj.uz

답안 #684925

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684925 2023-01-22T20:53:09 Z KiriLL1ca Segments (IZhO18_segments) C++17
100 / 100
 1846 ms 23136 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
#define pb push_back
#define fr first
#define sc second
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;

#define int long long

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;

template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }

template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const int N = 2e5 + 100;
const int buben = 1000;
const int nb = N / buben + 2;

struct segment {
    int l, r;
    segment (int l = 0, int r = 0) : l(l), r(r) {}
    inline int len () { return r - l + 1; }

    inline bool operator < (segment &x) {
        if (len() != x.len()) return len() < x.len();
        return make_pair(l, r) < make_pair(x.l, x.r);
    }
};

inline int inter (const segment &a, const segment &b) {
    return max(0ll, min(a.r, b.r) - max(a.l, b.l) + 1);
}

struct sex {
    vector <segment> buf;
    vector <segment> ful;
    vector <int> lb[nb], rb[nb];

    inline void add (int l, int r) {
        segment seg (l, r); buf.pb(seg);

        if (sz(buf) == buben) {
            sort(all(buf));

            vector <segment> mt; mt.reserve(sz(ful) + sz(buf));
            int uk1 = 0, uk2 = 0;
            while (uk1 < sz(ful) || uk2 < sz(buf)) {
                if (uk1 == sz(ful)) mt.pb(buf[uk2++]);
                else if (uk2 == sz(buf)) mt.pb(ful[uk1++]);
                else if (ful[uk1] < buf[uk2]) mt.pb(ful[uk1++]);
                else mt.pb(buf[uk2++]);
            }
            ful.swap(mt); buf.clear();

            for (int i = 0; i < nb; ++i) lb[i].clear(), rb[i].clear();
            for (int i = 0; i < sz(ful); ++i) {
                lb[i / buben].pb(ful[i].l);
                rb[i / buben].pb(ful[i].r);
            }
            for (int i = 0; i < nb; ++i) {
                sort(all(lb[i]));
                sort(all(rb[i]));
            }
        }
    }

    inline int get (int l, int r, int k) {
        int res = 0;
        segment seg (l, r);

        for (segment x : buf) res += inter(x, seg) >= k;

        for (int L = 0, i = 0; L < sz(ful); L += buben, ++i) {
            int R = min(sz(ful), L + buben) - 1;
            if (ful[L].len() >= k) {
                res += R - L + 1;
                res -= sz(lb[i]) - (lower_bound(all(lb[i]), r - k + 2) - lb[i].begin());
                res -= upper_bound(all(rb[i]), l + k - 2) - rb[i].begin();
            }
            else if (ful[R].len() >= k) {
                for (int j = L; j <= R; ++j) res += inter(ful[j], seg) >= k;
            }
        }

        return res;
    }
};

inline void solve () {
    int q, T; cin >> q >> T;
    vector <pii> seg (q); int uk = 0;
    int lst = 0;
    sex in, out;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int l, r; cin >> l >> r;
            l = (l ^ (T * lst)), r = (r ^ (T * lst)); if (l > r) swap(l, r);
            seg[uk++] = {l, r};
            in.add(l, r);
        }
        if (t == 2) {
            int id; cin >> id; --id;
            auto [l, r] = seg[id];
            out.add(l, r);
        }
        if (t == 3) {
            int l, r, k; cin >> l >> r >> k;
            l = (l ^ (T * lst)), r = (r ^ (T * lst)); if (l > r) swap(l, r);
            lst = in.get(l, r, k) - out.get(l, r, k);
            cout << lst << endl;
        }
    }
}

signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL

    int t = 1; // cin >> t;
    while (t--) solve();
    return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 9 ms 464 KB Output is correct
4 Correct 9 ms 596 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 9 ms 708 KB Output is correct
7 Correct 9 ms 604 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 5 ms 728 KB Output is correct
11 Correct 13 ms 672 KB Output is correct
12 Correct 12 ms 600 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 6 ms 604 KB Output is correct
15 Correct 10 ms 636 KB Output is correct
16 Correct 9 ms 596 KB Output is correct
17 Correct 8 ms 668 KB Output is correct
18 Correct 5 ms 880 KB Output is correct
19 Correct 8 ms 664 KB Output is correct
20 Correct 8 ms 596 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 4188 KB Output is correct
2 Correct 549 ms 6420 KB Output is correct
3 Correct 557 ms 6420 KB Output is correct
4 Correct 551 ms 6612 KB Output is correct
5 Correct 497 ms 8632 KB Output is correct
6 Correct 493 ms 8764 KB Output is correct
7 Correct 542 ms 6544 KB Output is correct
8 Correct 542 ms 6452 KB Output is correct
9 Correct 553 ms 6424 KB Output is correct
10 Correct 450 ms 5904 KB Output is correct
11 Correct 433 ms 6120 KB Output is correct
12 Correct 503 ms 7140 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 327 ms 4636 KB Output is correct
2 Correct 326 ms 4672 KB Output is correct
3 Correct 328 ms 4668 KB Output is correct
4 Correct 330 ms 4716 KB Output is correct
5 Correct 507 ms 5288 KB Output is correct
6 Correct 508 ms 4780 KB Output is correct
7 Correct 505 ms 5024 KB Output is correct
8 Correct 499 ms 6460 KB Output is correct
9 Correct 475 ms 6460 KB Output is correct
10 Correct 426 ms 6148 KB Output is correct
11 Correct 350 ms 6848 KB Output is correct
12 Correct 424 ms 6264 KB Output is correct
13 Correct 383 ms 6408 KB Output is correct
14 Correct 333 ms 6116 KB Output is correct
15 Correct 328 ms 6320 KB Output is correct
16 Correct 325 ms 5548 KB Output is correct
17 Correct 458 ms 4320 KB Output is correct
18 Correct 513 ms 4160 KB Output is correct
19 Correct 503 ms 4184 KB Output is correct
20 Correct 451 ms 4228 KB Output is correct
21 Correct 332 ms 6712 KB Output is correct
22 Correct 389 ms 6020 KB Output is correct
23 Correct 407 ms 6368 KB Output is correct
24 Correct 378 ms 6112 KB Output is correct
25 Correct 329 ms 4644 KB Output is correct
26 Correct 331 ms 4652 KB Output is correct
27 Correct 331 ms 4724 KB Output is correct
28 Correct 333 ms 4640 KB Output is correct
29 Correct 406 ms 6228 KB Output is correct
30 Correct 402 ms 6116 KB Output is correct
31 Correct 467 ms 6396 KB Output is correct
32 Correct 432 ms 6200 KB Output is correct
33 Correct 389 ms 6416 KB Output is correct
34 Correct 325 ms 5736 KB Output is correct
35 Correct 364 ms 6492 KB Output is correct
36 Correct 399 ms 6552 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 4572 KB Output is correct
2 Correct 427 ms 6672 KB Output is correct
3 Correct 415 ms 6756 KB Output is correct
4 Correct 418 ms 6688 KB Output is correct
5 Correct 519 ms 7440 KB Output is correct
6 Correct 489 ms 6132 KB Output is correct
7 Correct 501 ms 7824 KB Output is correct
8 Correct 486 ms 6144 KB Output is correct
9 Correct 425 ms 8228 KB Output is correct
10 Correct 454 ms 8396 KB Output is correct
11 Correct 424 ms 8380 KB Output is correct
12 Correct 475 ms 8804 KB Output is correct
13 Correct 433 ms 8528 KB Output is correct
14 Correct 422 ms 8020 KB Output is correct
15 Correct 486 ms 8624 KB Output is correct
16 Correct 441 ms 8600 KB Output is correct
17 Correct 543 ms 6388 KB Output is correct
18 Correct 547 ms 6564 KB Output is correct
19 Correct 545 ms 6644 KB Output is correct
20 Correct 540 ms 6472 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 9 ms 464 KB Output is correct
4 Correct 9 ms 596 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 9 ms 708 KB Output is correct
7 Correct 9 ms 604 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 5 ms 728 KB Output is correct
11 Correct 13 ms 672 KB Output is correct
12 Correct 12 ms 600 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 6 ms 604 KB Output is correct
15 Correct 10 ms 636 KB Output is correct
16 Correct 9 ms 596 KB Output is correct
17 Correct 8 ms 668 KB Output is correct
18 Correct 5 ms 880 KB Output is correct
19 Correct 8 ms 664 KB Output is correct
20 Correct 8 ms 596 KB Output is correct
21 Correct 537 ms 4188 KB Output is correct
22 Correct 549 ms 6420 KB Output is correct
23 Correct 557 ms 6420 KB Output is correct
24 Correct 551 ms 6612 KB Output is correct
25 Correct 497 ms 8632 KB Output is correct
26 Correct 493 ms 8764 KB Output is correct
27 Correct 542 ms 6544 KB Output is correct
28 Correct 542 ms 6452 KB Output is correct
29 Correct 553 ms 6424 KB Output is correct
30 Correct 450 ms 5904 KB Output is correct
31 Correct 433 ms 6120 KB Output is correct
32 Correct 503 ms 7140 KB Output is correct
33 Correct 415 ms 4572 KB Output is correct
34 Correct 427 ms 6672 KB Output is correct
35 Correct 415 ms 6756 KB Output is correct
36 Correct 418 ms 6688 KB Output is correct
37 Correct 519 ms 7440 KB Output is correct
38 Correct 489 ms 6132 KB Output is correct
39 Correct 501 ms 7824 KB Output is correct
40 Correct 486 ms 6144 KB Output is correct
41 Correct 425 ms 8228 KB Output is correct
42 Correct 454 ms 8396 KB Output is correct
43 Correct 424 ms 8380 KB Output is correct
44 Correct 475 ms 8804 KB Output is correct
45 Correct 433 ms 8528 KB Output is correct
46 Correct 422 ms 8020 KB Output is correct
47 Correct 486 ms 8624 KB Output is correct
48 Correct 441 ms 8600 KB Output is correct
49 Correct 543 ms 6388 KB Output is correct
50 Correct 547 ms 6564 KB Output is correct
51 Correct 545 ms 6644 KB Output is correct
52 Correct 540 ms 6472 KB Output is correct
53 Correct 416 ms 6784 KB Output is correct
54 Correct 425 ms 6744 KB Output is correct
55 Correct 420 ms 6684 KB Output is correct
56 Correct 410 ms 6648 KB Output is correct
57 Correct 522 ms 6028 KB Output is correct
58 Correct 369 ms 5928 KB Output is correct
59 Correct 499 ms 6692 KB Output is correct
60 Correct 437 ms 5788 KB Output is correct
61 Correct 439 ms 8484 KB Output is correct
62 Correct 478 ms 8604 KB Output is correct
63 Correct 481 ms 8652 KB Output is correct
64 Correct 477 ms 8556 KB Output is correct
65 Correct 413 ms 7748 KB Output is correct
66 Correct 417 ms 8292 KB Output is correct
67 Correct 439 ms 8584 KB Output is correct
68 Correct 429 ms 8412 KB Output is correct
69 Correct 540 ms 6388 KB Output is correct
70 Correct 553 ms 6476 KB Output is correct
71 Correct 561 ms 6520 KB Output is correct
72 Correct 544 ms 6440 KB Output is correct
73 Correct 416 ms 7608 KB Output is correct
74 Correct 432 ms 8456 KB Output is correct
75 Correct 486 ms 8792 KB Output is correct
76 Correct 487 ms 8872 KB Output is correct
77 Correct 421 ms 6812 KB Output is correct
78 Correct 429 ms 6636 KB Output is correct
79 Correct 408 ms 6692 KB Output is correct
80 Correct 414 ms 6688 KB Output is correct
81 Correct 431 ms 8396 KB Output is correct
82 Correct 419 ms 7568 KB Output is correct
83 Correct 414 ms 8748 KB Output is correct
84 Correct 461 ms 8428 KB Output is correct
85 Correct 452 ms 8476 KB Output is correct
86 Correct 449 ms 8520 KB Output is correct
87 Correct 417 ms 8152 KB Output is correct
88 Correct 406 ms 8168 KB Output is correct

Subtask #6
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 9 ms 464 KB Output is correct
4 Correct 9 ms 596 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 9 ms 708 KB Output is correct
7 Correct 9 ms 604 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 5 ms 728 KB Output is correct
11 Correct 13 ms 672 KB Output is correct
12 Correct 12 ms 600 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 6 ms 604 KB Output is correct
15 Correct 10 ms 636 KB Output is correct
16 Correct 9 ms 596 KB Output is correct
17 Correct 8 ms 668 KB Output is correct
18 Correct 5 ms 880 KB Output is correct
19 Correct 8 ms 664 KB Output is correct
20 Correct 8 ms 596 KB Output is correct
21 Correct 537 ms 4188 KB Output is correct
22 Correct 549 ms 6420 KB Output is correct
23 Correct 557 ms 6420 KB Output is correct
24 Correct 551 ms 6612 KB Output is correct
25 Correct 497 ms 8632 KB Output is correct
26 Correct 493 ms 8764 KB Output is correct
27 Correct 542 ms 6544 KB Output is correct
28 Correct 542 ms 6452 KB Output is correct
29 Correct 553 ms 6424 KB Output is correct
30 Correct 450 ms 5904 KB Output is correct
31 Correct 433 ms 6120 KB Output is correct
32 Correct 503 ms 7140 KB Output is correct
33 Correct 327 ms 4636 KB Output is correct
34 Correct 326 ms 4672 KB Output is correct
35 Correct 328 ms 4668 KB Output is correct
36 Correct 330 ms 4716 KB Output is correct
37 Correct 507 ms 5288 KB Output is correct
38 Correct 508 ms 4780 KB Output is correct
39 Correct 505 ms 5024 KB Output is correct
40 Correct 499 ms 6460 KB Output is correct
41 Correct 475 ms 6460 KB Output is correct
42 Correct 426 ms 6148 KB Output is correct
43 Correct 350 ms 6848 KB Output is correct
44 Correct 424 ms 6264 KB Output is correct
45 Correct 383 ms 6408 KB Output is correct
46 Correct 333 ms 6116 KB Output is correct
47 Correct 328 ms 6320 KB Output is correct
48 Correct 325 ms 5548 KB Output is correct
49 Correct 458 ms 4320 KB Output is correct
50 Correct 513 ms 4160 KB Output is correct
51 Correct 503 ms 4184 KB Output is correct
52 Correct 451 ms 4228 KB Output is correct
53 Correct 332 ms 6712 KB Output is correct
54 Correct 389 ms 6020 KB Output is correct
55 Correct 407 ms 6368 KB Output is correct
56 Correct 378 ms 6112 KB Output is correct
57 Correct 329 ms 4644 KB Output is correct
58 Correct 331 ms 4652 KB Output is correct
59 Correct 331 ms 4724 KB Output is correct
60 Correct 333 ms 4640 KB Output is correct
61 Correct 406 ms 6228 KB Output is correct
62 Correct 402 ms 6116 KB Output is correct
63 Correct 467 ms 6396 KB Output is correct
64 Correct 432 ms 6200 KB Output is correct
65 Correct 389 ms 6416 KB Output is correct
66 Correct 325 ms 5736 KB Output is correct
67 Correct 364 ms 6492 KB Output is correct
68 Correct 399 ms 6552 KB Output is correct
69 Correct 415 ms 4572 KB Output is correct
70 Correct 427 ms 6672 KB Output is correct
71 Correct 415 ms 6756 KB Output is correct
72 Correct 418 ms 6688 KB Output is correct
73 Correct 519 ms 7440 KB Output is correct
74 Correct 489 ms 6132 KB Output is correct
75 Correct 501 ms 7824 KB Output is correct
76 Correct 486 ms 6144 KB Output is correct
77 Correct 425 ms 8228 KB Output is correct
78 Correct 454 ms 8396 KB Output is correct
79 Correct 424 ms 8380 KB Output is correct
80 Correct 475 ms 8804 KB Output is correct
81 Correct 433 ms 8528 KB Output is correct
82 Correct 422 ms 8020 KB Output is correct
83 Correct 486 ms 8624 KB Output is correct
84 Correct 441 ms 8600 KB Output is correct
85 Correct 543 ms 6388 KB Output is correct
86 Correct 547 ms 6564 KB Output is correct
87 Correct 545 ms 6644 KB Output is correct
88 Correct 540 ms 6472 KB Output is correct
89 Correct 416 ms 6784 KB Output is correct
90 Correct 425 ms 6744 KB Output is correct
91 Correct 420 ms 6684 KB Output is correct
92 Correct 410 ms 6648 KB Output is correct
93 Correct 522 ms 6028 KB Output is correct
94 Correct 369 ms 5928 KB Output is correct
95 Correct 499 ms 6692 KB Output is correct
96 Correct 437 ms 5788 KB Output is correct
97 Correct 439 ms 8484 KB Output is correct
98 Correct 478 ms 8604 KB Output is correct
99 Correct 481 ms 8652 KB Output is correct
100 Correct 477 ms 8556 KB Output is correct
101 Correct 413 ms 7748 KB Output is correct
102 Correct 417 ms 8292 KB Output is correct
103 Correct 439 ms 8584 KB Output is correct
104 Correct 429 ms 8412 KB Output is correct
105 Correct 540 ms 6388 KB Output is correct
106 Correct 553 ms 6476 KB Output is correct
107 Correct 561 ms 6520 KB Output is correct
108 Correct 544 ms 6440 KB Output is correct
109 Correct 416 ms 7608 KB Output is correct
110 Correct 432 ms 8456 KB Output is correct
111 Correct 486 ms 8792 KB Output is correct
112 Correct 487 ms 8872 KB Output is correct
113 Correct 421 ms 6812 KB Output is correct
114 Correct 429 ms 6636 KB Output is correct
115 Correct 408 ms 6692 KB Output is correct
116 Correct 414 ms 6688 KB Output is correct
117 Correct 431 ms 8396 KB Output is correct
118 Correct 419 ms 7568 KB Output is correct
119 Correct 414 ms 8748 KB Output is correct
120 Correct 461 ms 8428 KB Output is correct
121 Correct 452 ms 8476 KB Output is correct
122 Correct 449 ms 8520 KB Output is correct
123 Correct 417 ms 8152 KB Output is correct
124 Correct 406 ms 8168 KB Output is correct
125 Correct 1202 ms 13080 KB Output is correct
126 Correct 1178 ms 13112 KB Output is correct
127 Correct 1200 ms 13112 KB Output is correct
128 Correct 1175 ms 13108 KB Output is correct
129 Correct 1176 ms 13232 KB Output is correct
130 Correct 1187 ms 13236 KB Output is correct
131 Correct 1113 ms 11344 KB Output is correct
132 Correct 1540 ms 12484 KB Output is correct
133 Correct 1701 ms 13324 KB Output is correct
134 Correct 1138 ms 11548 KB Output is correct
135 Correct 1788 ms 13472 KB Output is correct
136 Correct 812 ms 10856 KB Output is correct
137 Correct 1761 ms 17052 KB Output is correct
138 Correct 1450 ms 16876 KB Output is correct
139 Correct 1623 ms 16792 KB Output is correct
140 Correct 1719 ms 16824 KB Output is correct
141 Correct 1540 ms 16624 KB Output is correct
142 Correct 1197 ms 21216 KB Output is correct
143 Correct 1240 ms 17588 KB Output is correct
144 Correct 1170 ms 23136 KB Output is correct
145 Correct 1719 ms 17428 KB Output is correct
146 Correct 1331 ms 16076 KB Output is correct
147 Correct 1243 ms 17888 KB Output is correct
148 Correct 1230 ms 17552 KB Output is correct
149 Correct 1625 ms 12852 KB Output is correct
150 Correct 1485 ms 12848 KB Output is correct
151 Correct 1623 ms 12720 KB Output is correct
152 Correct 1648 ms 12836 KB Output is correct
153 Correct 1500 ms 12812 KB Output is correct
154 Correct 1650 ms 12864 KB Output is correct
155 Correct 1248 ms 16188 KB Output is correct
156 Correct 1281 ms 16940 KB Output is correct
157 Correct 1757 ms 17244 KB Output is correct
158 Correct 1781 ms 17148 KB Output is correct
159 Correct 1501 ms 16592 KB Output is correct
160 Correct 1396 ms 16076 KB Output is correct
161 Correct 1192 ms 13300 KB Output is correct
162 Correct 1197 ms 13036 KB Output is correct
163 Correct 1200 ms 13112 KB Output is correct
164 Correct 1213 ms 15256 KB Output is correct
165 Correct 1205 ms 13024 KB Output is correct
166 Correct 1185 ms 13160 KB Output is correct
167 Correct 1846 ms 17176 KB Output is correct
168 Correct 1816 ms 17328 KB Output is correct
169 Correct 1730 ms 16848 KB Output is correct
170 Correct 1676 ms 17144 KB Output is correct
171 Correct 1541 ms 16624 KB Output is correct
172 Correct 1328 ms 15912 KB Output is correct
173 Correct 1747 ms 16860 KB Output is correct
174 Correct 1330 ms 16140 KB Output is correct
175 Correct 1578 ms 16748 KB Output is correct
176 Correct 1244 ms 15152 KB Output is correct
177 Correct 1483 ms 16776 KB Output is correct
178 Correct 1415 ms 16848 KB Output is correct