oj.uz

Submission #516531

# Submission time Handle Problem Language Result Execution time Memory
516531 2022-01-21T12:51:55 Z Dasha_Gnedko Segments (IZhO18_segments) C++17
23 / 100
 449 ms 65540 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

using namespace std;

using namespace __gnu_pbds;
template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(time(0));

#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long

const int N = 1e5 + 100;
const int M = 31;
const int mod = 998244353;
const int inf = 1e9 + 7;

vector < int > ve;

struct Fenwick
{
    ordered_set < pair < int, int > > f[N];
    int n, state = 0;

    void build()
    {
        n = sz(ve);
//        f.resize(n);
    }

    void upd(int k, pair < int, int > p, int fl)
    {
        int l = 0, r = sz(ve) - 1, i = n;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (ve[mid] <= k)
            {
                i = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        for(; i < n; i = (i | (i + 1)))
        {
            if (fl) f[i].insert(p);
            else f[i].erase(p);
        }
    }

    int sum(int i, pair < int, int > p)
    {
        int ans = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1)
            ans += f[i].order_of_key(p);
        return ans;
    }

    int get_ans(int i, int l, int r)
    {
        int ans = sum(i, {r + 1, -1});
        if (l) ans -= sum(i, {l, -1});
        return ans;
    }

    int get(int l, int r, int k)
    {
        if (l > r) return 0;
        int ans = get_ans(n - 1, l, r);
        int le = 0, ri = sz(ve) - 1, i = -1;
        while (le <= ri)
        {
            int mid = (le + ri) / 2;
            if (ve[mid] <= k)
            {
                i = mid;
                le = mid + 1;
            }
            else ri = mid - 1;
        }
        if (i) ans -= get_ans(i - 1, l, r);
        return ans;
    }

    int get1(int l, int r, int k)
    {
        if (l > r) return 0;
        int le = 0, ri = sz(ve) - 1, i = -1;
        while (le <= ri)
        {
            int mid = (le + ri) / 2;
            if (ve[mid] <= k)
            {
                i = mid;
                le = mid + 1;
            }
            else ri = mid - 1;
        }
        return get_ans(i, l, r);
    }

    int get2(int r, int k)
    {
        if (r < 0) return 0;
        int le = 0, ri = sz(ve) - 1, i = -1;
        while (le <= ri)
        {
            int mid = (le + ri) / 2;
            if (ve[mid] <= k)
            {
                i = mid;
                le = mid + 1;
            }
            else ri = mid - 1;
        }
        return sum(i, {r + 1, -1});
    }
};

Fenwick f1, f2;
vector < pair < pair < int, int >, pair < int, int > > > ask;
//ordered_set < pair < int, int > > st1, st2;

int32_t 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);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL

    int q, T;
    cin >> q >> T;
    for(int i = 0; i < q; i++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int l, r;
            cin >> l >> r;
            ask.pb({{type, l}, {r, -1}});
        }
        if (type == 2)
        {
            int id;
            cin >> id;
            id--;
            ask.pb({{type, id}, {-1, -1}});
        }
        if (type == 3)
        {
            int l, r, k;
            cin >> l >> r >> k;
            ask.pb({{type, l}, {r, k}});
            ve.pb(k);
        }
    }
    ve.pb(1);
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    f1.build();
    f2.build();
    f2.state = 1;
    vector < pair < int, int > > a;
    int ans = 0;
    for(auto to: ask)
    {
        int type = to.F.F;
        if (type == 1)
        {
            int l = to.F.S, r = to.S.F;
            l = (l ^ (T * ans));
            r = (r ^ (T * ans));
            if (l > r) swap(l, r);
            f1.upd(r - l + 1, {l, sz(a)}, 1);
            f2.upd(r - l + 1, {r, sz(a)}, 1);
//            st1.insert({l, sz(a)});
//            st2.insert({r, sz(a)});
            a.pb({l, r});
        }
        if (type == 2)
        {
            int id = to.F.S;
            int l = a[id].F, r = a[id].S;
            f1.upd(r - l + 1, {l, id}, 0);
            f2.upd(r - l + 1, {r, id}, 0);
//            st1.erase({l, id});
//            st2.erase({r, id});
        }
        if (type == 3)
        {
            int l = to.F.S, r = to.S.F, k = to.S.S;
            l = (l ^ (T * ans));
            r = (r ^ (T * ans));
            if (l > r) swap(l, r);
            ans = 0;
            if (r - l + 1 < k)
            {
                cout << 0 << endl;
                continue;
            }
            ans += f1.get(l + 1, r - k + 1, k);
            ans += f1.get1(0, l, 2e9 + 1);
            ans -= f2.get1(0, l + k - 2, 2e9 + 1);
            if (l + k - 2 >= l) ans += f2.get2(l + k - 2, k - 1);
            ans -= f1.get1(0, l, k - 1);
            cout << ans << endl;
        }
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19112 KB Output is correct
2 Correct 15 ms 19120 KB Output is correct
3 Correct 22 ms 19276 KB Output is correct
4 Correct 20 ms 19276 KB Output is correct
5 Correct 35 ms 21516 KB Output is correct
6 Correct 33 ms 21464 KB Output is correct
7 Correct 29 ms 19744 KB Output is correct
8 Correct 38 ms 20772 KB Output is correct
9 Correct 40 ms 20176 KB Output is correct
10 Correct 33 ms 20528 KB Output is correct
11 Correct 32 ms 20932 KB Output is correct
12 Correct 38 ms 20896 KB Output is correct
13 Correct 29 ms 21264 KB Output is correct
14 Correct 29 ms 20556 KB Output is correct
15 Correct 26 ms 19324 KB Output is correct
16 Correct 32 ms 19336 KB Output is correct
17 Correct 38 ms 20028 KB Output is correct
18 Correct 30 ms 21192 KB Output is correct
19 Correct 28 ms 19920 KB Output is correct
20 Correct 32 ms 19916 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 449 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 21716 KB Output is correct
2 Correct 79 ms 21784 KB Output is correct
3 Correct 96 ms 21792 KB Output is correct
4 Correct 67 ms 21792 KB Output is correct
5 Correct 163 ms 30464 KB Output is correct
6 Correct 168 ms 29136 KB Output is correct
7 Correct 164 ms 30236 KB Output is correct
8 Correct 171 ms 33236 KB Output is correct
9 Correct 154 ms 32636 KB Output is correct
10 Correct 167 ms 30000 KB Output is correct
11 Correct 91 ms 22128 KB Output is correct
12 Correct 158 ms 30088 KB Output is correct
13 Correct 167 ms 29116 KB Output is correct
14 Correct 164 ms 25136 KB Output is correct
15 Correct 117 ms 24544 KB Output is correct
16 Correct 109 ms 23556 KB Output is correct
17 Correct 144 ms 27808 KB Output is correct
18 Correct 179 ms 27820 KB Output is correct
19 Correct 162 ms 27780 KB Output is correct
20 Correct 142 ms 27776 KB Output is correct
21 Correct 97 ms 22284 KB Output is correct
22 Correct 143 ms 25776 KB Output is correct
23 Correct 132 ms 27956 KB Output is correct
24 Correct 163 ms 26164 KB Output is correct
25 Correct 74 ms 21812 KB Output is correct
26 Correct 81 ms 21780 KB Output is correct
27 Correct 73 ms 21824 KB Output is correct
28 Correct 71 ms 21764 KB Output is correct
29 Correct 185 ms 28508 KB Output is correct
30 Correct 160 ms 28600 KB Output is correct
31 Correct 176 ms 32808 KB Output is correct
32 Correct 206 ms 30076 KB Output is correct
33 Correct 161 ms 29348 KB Output is correct
34 Correct 142 ms 24492 KB Output is correct
35 Correct 143 ms 27248 KB Output is correct
36 Correct 145 ms 29740 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 21760 KB Output is correct
2 Correct 169 ms 21708 KB Output is correct
3 Correct 180 ms 21848 KB Output is correct
4 Correct 199 ms 21804 KB Output is correct
5 Runtime error 439 ms 65540 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19112 KB Output is correct
2 Correct 15 ms 19120 KB Output is correct
3 Correct 22 ms 19276 KB Output is correct
4 Correct 20 ms 19276 KB Output is correct
5 Correct 35 ms 21516 KB Output is correct
6 Correct 33 ms 21464 KB Output is correct
7 Correct 29 ms 19744 KB Output is correct
8 Correct 38 ms 20772 KB Output is correct
9 Correct 40 ms 20176 KB Output is correct
10 Correct 33 ms 20528 KB Output is correct
11 Correct 32 ms 20932 KB Output is correct
12 Correct 38 ms 20896 KB Output is correct
13 Correct 29 ms 21264 KB Output is correct
14 Correct 29 ms 20556 KB Output is correct
15 Correct 26 ms 19324 KB Output is correct
16 Correct 32 ms 19336 KB Output is correct
17 Correct 38 ms 20028 KB Output is correct
18 Correct 30 ms 21192 KB Output is correct
19 Correct 28 ms 19920 KB Output is correct
20 Correct 32 ms 19916 KB Output is correct
21 Runtime error 449 ms 65540 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19112 KB Output is correct
2 Correct 15 ms 19120 KB Output is correct
3 Correct 22 ms 19276 KB Output is correct
4 Correct 20 ms 19276 KB Output is correct
5 Correct 35 ms 21516 KB Output is correct
6 Correct 33 ms 21464 KB Output is correct
7 Correct 29 ms 19744 KB Output is correct
8 Correct 38 ms 20772 KB Output is correct
9 Correct 40 ms 20176 KB Output is correct
10 Correct 33 ms 20528 KB Output is correct
11 Correct 32 ms 20932 KB Output is correct
12 Correct 38 ms 20896 KB Output is correct
13 Correct 29 ms 21264 KB Output is correct
14 Correct 29 ms 20556 KB Output is correct
15 Correct 26 ms 19324 KB Output is correct
16 Correct 32 ms 19336 KB Output is correct
17 Correct 38 ms 20028 KB Output is correct
18 Correct 30 ms 21192 KB Output is correct
19 Correct 28 ms 19920 KB Output is correct
20 Correct 32 ms 19916 KB Output is correct
21 Runtime error 449 ms 65540 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -