oj.uz

Submission #335318

# Submission time Handle Problem Language Result Execution time Memory
335318 2020-12-12T00:12:29 Z limabeans Segments (IZhO18_segments) C++17
0 / 100
 360 ms 3908 KB 
#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) {
	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;
	    res += e-i+1;
	    
	    if (w[i].r-w[i].l+1 >= k) {
		res -= (lower_bound(R[i/B].begin(),R[i/B].end(),i+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=e; j>=i; j--) {
		    if (w[j].r-w[j].l+1<k) break;
		    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 7 ms 620 KB Output is correct
4 Incorrect 7 ms 620 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 7 ms 620 KB Output is correct
4 Incorrect 7 ms 620 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 7 ms 620 KB Output is correct
4 Incorrect 7 ms 620 KB Output isn't correct
5 Halted 0 ms 0 KB -