제출 #441021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441021		Redhood	Segments (IZhO18_segments)	C++14	75 / 100	3522 ms	46204 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 = 2000;
const int C = buben*4;
int L[N], R[N];
int memory[N];
int oukek[N/buben+1];
struct sofuckinsmart{
    vector<int>ID[N/buben+1],X[N/buben+1],Y[N/buben+1];
    set<pair<int,int>>Xid,Yid;
    int numofblock[N], YV[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();
        int n = len(Xid);


        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);
            }else{
                int left = n - max(0,((n-1)/buben-1)+1)*buben;
                X[i].resize(left);
                ID[i].resize(left);
                Y[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][oukek[idb]++] = 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 < 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);
                numofblock[id] = idb;
                break;
            }
        }
        done++;
        if(done == C){
            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 < 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;
    }
}Slen, Sr;

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;
            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: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 0 / 25