Submission #335324

#	Time	Username	Problem	Language	Result	Execution time	Memory
335324		limabeans	Segments (IZhO18_segments)	C++17	100 / 100	2520 ms	10380 KiB

segments

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl












const int maxn = 1e6 + 10;

struct interval {
    int l,r;
    bool operator<(const interval& o) const {
	return r-l<o.r-o.l;
    }
};


const int B = 1500;


struct {
    vector<interval> v;

    vector<interval> w;
    vector<vector<int>> L, R;

    void rebuild() {
	w.insert(w.end(),v.begin(),v.end());
	sort(w.begin(),w.end());
	v.clear();

	int len = w.size();
	L.clear();
	R.clear();
	L.resize(len/B);
	R.resize(len/B);

	for (int i=0; i<len; i++) {
	    L[i/B].push_back(w[i].l);
	    R[i/B].push_back(w[i].r);
	}

	for (auto &p: L) {
	    sort(p.begin(),p.end());
	}
	for (auto &p: R) {
	    sort(p.begin(),p.end());
	}
    }
    
    void insert(int l, int r) {
	v.push_back({l,r});
	if ((int)v.size()==B) {
	    rebuild();
	}
    }


    int solve(int l, int r, int k) {
	if (r-l+1<k) return 0;
	int res = 0;
	for (auto p: v) {
	    res += (min(r,p.r)-max(l,p.l)+1>=k);
	}

	assert((int)w.size()%B==0);
	for (int i=0; i+B<=(int)w.size(); i+=B) {
	    int e = i+B-1;
	    if (w[i].r-w[i].l+1 >= k) {
		res += e-i+1;
		res -= (lower_bound(R[i/B].begin(),R[i/B].end(),l+k-1)-R[i/B].begin()); // end too early
		res -= (L[i/B].end() - upper_bound(L[i/B].begin(),L[i/B].end(),r-k+1)); // start too late
	    } else if (w[e].r-w[e].l+1 >= k) {
		for (int j=i; j<=e; j++) {
		    if (min(w[j].r,r)-max(w[j].l,l)+1 >= k) {
			res++;
		    }
		}
	    }
	}

	return res;
    }
} alive, dead;



int n,t;
int lastans=0;

interval arr[maxn];
int idx=0;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>t;

    while (n--) {
	int op;
	cin>>op;
	if (op==1) {
	    int a,b;
	    cin>>a>>b;
	    int l=a^(t*lastans);
	    int r=b^(t*lastans);
	    if (l>r) swap(l,r);
	    arr[++idx] = interval{l,r};
	    alive.insert(arr[idx].l,arr[idx].r);
	} else if (op==2) {
	    int id;
	    cin>>id;
	    dead.insert(arr[id].l,arr[id].r);
	} else if (op==3) {
	    int a,b,k;
	    cin>>a>>b>>k;
	    int l=a^(t*lastans);
	    int r=b^(t*lastans);
	    if (l>r) swap(l,r);
	    lastans = alive.solve(l,r,k) - dead.solve(l,r,k);
	    cout<<lastans<<"\n";
	} else assert(false);
    }
    
    
    return 0;
}

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