Submission #441011

#	Time	Username	Problem	Language	Result	Execution time	Memory
441011		Redhood	Segments (IZhO18_segments)	C++14	0 / 100	541 ms	26652 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 = 1800;
int L[N], R[N];
struct sofuckinsmart{
    vector<vector<int>>ID,X,Y;
    set<pair<int,int>>Xid,Yid;
    int memory[N], numofblock[N], YV[N];
    int done = 0;
    sofuckinsmart(){
        X.pb({});
        ID.pb({});
        Y.pb({});
    }
    void rebuild(){
        cerr << "rebuild start\n";
        ///i love this trick, yup
        ID.clear();
        X.clear();
        Y.clear();

        int n = len(Xid);
        n = max(n , 1);
        ID.resize((n-1)/buben + 1);
        X.resize((n-1)/buben + 1);
        Y.resize((n-1)/buben + 1);

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


        int ind=0;
        for(auto u : Xid){
            memory[u.se] = ind;
            ind++;
        }
        for(auto u : Yid){
            int idb = memory[u.se]/buben, ps = memory[u.se]%buben;
            ID[idb][ps] = u.se;
            X[idb][ps] = L[u.se];
            Y[idb].pb(u.fi);
            numofblock[u.se]=idb;
        }
//        for(int i = 0 ; i <= (n-1)/buben; ++i)
//            sort(all(Y[i])), sort(all(X[i]));
        cerr << "rebuild done\n";
    }
    void add(int id, int y){
        int x = L[id];
        Xid.insert({x , id});
        Yid.insert({y , id});
        YV[id] = y;
        for(int idb = 0; idb < len(Y); ++idb){
            if(idb == len(X)-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);
                numofblock[id] = idb;
                break;
            }
        }
        done++;
        if(done == buben){
            done = 0;
            rebuild();
        }
    }
    void del(int id, int y){
        int x = L[id];
        Xid.erase({x , id});
        Yid.erase({y , 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));
                ID[idb].erase(ID[idb].begin()+i);
                break;
            }
        }
        assert(found);
    }
    int qry(int Lx, int Rx, int Yl){
        if(Lx > Rx)
            return 0;
        int ans = 0;
        for(int idb = 0 ; idb < len(X); ++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;
                if(X[idb][0] >= Lx){
                    for(int i = 0 ; i < len(X[idb]); ++i){
                        if(X[idb][i] > Rx)
                            break;
                        if(YV[ID[idb][i]] >= Yl)
                            ans++;
                    }
                }else{
                    assert(X[idb].back() >= Lx && X[idb].back() <= Rx);
                    for(int i = len(X[idb])-1 ; i >= 0; --i){
                        if(X[idb][i] < Lx)
                            break;
                        if(YV[ID[idb][i]] >= Yl)
                            ans++;
                    }
                }
            }
        }
        return ans;
    }
}Slen, Sr;

signed main(){
    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;
            Slen.add(lst, R[lst]-L[lst]+1);
            Sr.add(lst , R[lst]);
            lst++;
        }
        if(type == 2){
            int id;cin >> id;
            Slen.del(id, R[id]-L[id]+1);
            Sr.del(id, R[id]);
        }
        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 = Slen.qry(a, b-k+1, k) + Sr.qry(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: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25