oj.uz

Submission #682617

# Submission time Handle Problem Language Result Execution time Memory
682617 2023-01-16T15:30:06 Z phoenix Segments (IZhO18_segments) C++17
15 / 100
 709 ms 6172 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = (1 << 17);
const int B = 317;
struct tree {
    vector<int> st[N / B + 10];
    vector<int> a;
    int sz = 0;
    void init(vector<int> &a) {
        this->a = a;
        sz = (int)a.size();
        build();
    }
    void build() {
        for(int i = 0; i < sz; i++) {
            st[i / B].push_back(a[i]);
        }
        for(int i = 0; i <= (sz - 1) / B; i++) 
            sort(st[i].begin(), st[i].end());
    }
    int get(int ql, int qr, int x) {
        int ans = 0;
        while(ql <= qr) {
            bool f = (ql % B == 0 && ql + B - 1 <= qr);
            if(f) {
                int lb = -1, rb = (int)st[ql / B].size();
                while(rb - lb > 1) {
                    int m = (lb + rb) / 2;
                    if(st[ql / B][m] < x) lb = m;
                    else rb = m;
                }
                ans += lb + 1;
                ql += B;
            } else {
                ans += (a[ql] < x);
                ql++;
            }
        }
        return ans;
    }
};
vector<pair<int, int>> v;
// left bounds, right bounds
vector<int> ll, rr;
tree t1, t2;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    int n, t;
    cin >> n >> t;
    int lastans = 0;
    bool isBuilt = 0;
    for(int i = 1; i <= n; i++) {
        int type;
        cin >> type;
        if(type == 1) {
            int l, r;
            cin >> l >> r;
            l = (l ^ (t * lastans));
            r = (r ^ (t * lastans));
            if(l > r) swap(l, r);
            v.push_back({l, r});
        } else {
            if(!isBuilt) {
                sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b){return a.second - a.first < b.second - b.first;});
                for(int i = 0; i < (int)v.size(); i++) {
                    ll.push_back(v[i].first);
                    rr.push_back(v[i].second);
                }
                t1.init(ll);
                t2.init(rr);
                isBuilt = 1;
            }
            int l, r, k;
            cin >> l >> r >> k;
            l = (l ^ (t * lastans));
            r = (r ^ (t * lastans));
            lastans = 0;
            if(l > r) swap(l, r);
            if(r - l + 1 < k) {
                cout << 0 << '\n';
                continue;
            }

            int lb = -1, rb = (int)v.size();
            while(rb - lb > 1) {
                int m = (lb + rb) / 2;
                if(v[m].second - v[m].first + 1 >= k) rb = m;
                else lb = m;
            }
            lastans = t1.get(rb, (int)v.size() - 1, r - k + 2) - t2.get(rb, (int)v.size() - 1, l + k - 1);
            cout << lastans << '\n';
        }
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 2440 KB Output is correct
2 Correct 679 ms 2416 KB Output is correct
3 Correct 705 ms 2320 KB Output is correct
4 Correct 677 ms 2584 KB Output is correct
5 Correct 192 ms 4020 KB Output is correct
6 Correct 134 ms 6172 KB Output is correct
7 Correct 692 ms 5052 KB Output is correct
8 Correct 696 ms 5308 KB Output is correct
9 Correct 675 ms 5072 KB Output is correct
10 Correct 498 ms 4464 KB Output is correct
11 Correct 555 ms 4616 KB Output is correct
12 Correct 632 ms 5796 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -