Submission #441030

#	Time	Username	Problem	Language	Result	Execution time	Memory
441030		Redhood	Segments (IZhO18_segments)	C++14	100 / 100	2673 ms	18456 KiB

segments

#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define len(x) (int)(x).size()
using namespace std;

/// x,y
const int N = (int)2e5 + 10;
const int buben = 1000;
const int C = buben*2;
int L[N], R[N];
int memory[N];
int oukek[N/buben+1];
    vector<int>ID[N/buben+1],X[N/buben+1],Y[N/buben+1],Ylen[N/buben+1];
    set < pair < int , int > > have;
    int numofblock[N], YV[N], YVlen[N];
    int done = 0;
    int blocks=1;
    void rebuild(){
//        cerr << "rebuild start\n";
        ///i love this trick, yup
        for(int x = 0; x < blocks; ++x)
            ID[x].clear(), X[x].clear(), Y[x].clear(), Ylen[x].clear();
        int n = len(have);


        assert(n >= 1);
        n = max(n , 1);
        blocks = (n-1)/buben+1;
        for(int i = 0; i <= (n-1)/buben; ++i){
            oukek[i]=0;
            if(i < (n-1)/buben){
                X[i].resize(buben);
                ID[i].resize(buben);
                Y[i].resize(buben);
                Ylen[i].resize(buben);
            }else{
                int left = n - max(0,((n-1)/buben-1)+1)*buben;
                X[i].resize(left);
                ID[i].resize(left);
                Y[i].resize(left);
                Ylen[i].resize(left);
            }
        }


        int ind=0;
        for(auto u : have){
            X[ind/buben][ind%buben] = L[u.se];
            ID[ind/buben][ind%buben] = u.se;
            Y[ind/buben][ind%buben] = R[u.se];
            Ylen[ind/buben][ind%buben] = R[u.se]-L[u.se]+1;
            numofblock[u.se] = ind/buben;
            ind++;
        }
        for(int i = 0 ; i <= (n-1)/buben; ++i)
            sort(all(Y[i])), sort(all(Ylen[i]));
    }
    void add(int id, int y, int Len){
        int x = L[id];
        have.insert({x , id});
        YV[id] = y;
        YVlen[id] = Len;
        for(int idb = 0; idb < blocks; ++idb){
            if(idb == blocks-1 || X[idb+1][0] >= x){
                int pos = lower_bound(all(X[idb]), x) - X[idb].begin();
                X[idb].insert(X[idb].begin()+pos, x);
                ID[idb].insert(ID[idb].begin()+pos, id);
                int ps1 = lower_bound(all(Y[idb]), y) - Y[idb].begin();
                Y[idb].insert(Y[idb].begin()+ps1, y);
                int ps2 = lower_bound(all(Ylen[idb]), Len) - Ylen[idb].begin();
                Ylen[idb].insert(Ylen[idb].begin()+ps2, Len);

                numofblock[id] = idb;
                break;
            }
        }
        done++;
        if(done == C){
            done = 0;
            rebuild();
        }
    }
    void del(int id, int y, int Len){
        int x = L[id];
        have.erase({x ,id});
        int idb = numofblock[id];
        bool found=0;
        for(int i=0;i<len(ID[idb]);++i){
            if(ID[idb][i] == id){
                found=1;
                X[idb].erase(lower_bound(all(X[idb]),x));
                Y[idb].erase(lower_bound(all(Y[idb]),y));
                Ylen[idb].erase(lower_bound(all(Ylen[idb]), Len));
                ID[idb].erase(ID[idb].begin()+i);
                break;
            }
        }
        assert(found);
    }
    int qryR(int Lx, int Rx, int Yl){
        if(Lx > Rx)
            return 0;
        int ans = 0;
        for(int idb = 0 ; idb < blocks; ++idb){
            if(X[idb][0] >= Lx && X[idb].back() <= Rx){
                ans += Y[idb].end() - lower_bound(all(Y[idb]), Yl);
            }else{
                if(X[idb][0] > Rx)
                    break;
                if(X[idb].back() < Lx)
                    continue;
                for(int i = 0 ; i < len(X[idb]); ++i){
                    if(X[idb][i] >= Lx && X[idb][i] <= Rx && YV[ID[idb][i]] >= Yl)
                        ans++;
                }
            }
        }
        return ans;
    }
    int qryLen(int Lx, int Rx, int Yl){
        if(Lx > Rx)
            return 0;
        int ans = 0;
        for(int idb = 0 ; idb < blocks; ++idb){
            if(X[idb][0] >= Lx && X[idb].back() <= Rx){
                ans += Ylen[idb].end() - lower_bound(all(Ylen[idb]), Yl);
            }else{
                if(X[idb][0] > Rx)
                    break;
                if(X[idb].back() < Lx)
                    continue;
                for(int i = 0 ; i < len(X[idb]); ++i){
                    if(X[idb][i] >= Lx && X[idb][i] <= Rx && YVlen[ID[idb][i]] >= Yl)
                        ans++;
                }
            }
        }
        return ans;
    }

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, t;
    cin >> n >> t;
    int lst = 1;
    int lastans = 0;
    for(int i = 0 ; i < n; ++i){
        int type;cin >> type;
        if(type == 1){
            int a,b;cin >> a >> b;
            a = a ^ (t * lastans);
            b = b ^ (t * lastans);
            if(a > b)swap(a , b);
            L[lst] = a, R[lst] = b;
            add(lst, R[lst], R[lst]-L[lst]+1);
            lst++;
        }
        if(type == 2){
            int id;cin >> id;
            del(id, R[id], R[id]-L[id]+1);
        }
        if(type == 3){
            int a,b,k;cin >> a >> b >> k;
            a = a ^ (t * lastans);
            b = b ^ (t * lastans);
            if(a > b)swap(a,b);
            int answer = qryLen(a, b-k+1, k) + qryR(0, a-1, a+k-1);
            cout << answer << '\n';
            lastans = answer;
        }
    }
    return 0;
}
/*
6 1
1 1 2
3 2 4 2
1 3 5
3 2 3 1
2 1
3 0 3 1

6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2
*/

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 25 / 25