Submission #129959

#	Time	Username	Problem	Language	Result	Execution time	Memory
129959		Adhyyan1252	Sails (IOI07_sails)	C++11	100 / 100	329 ms	6036 KiB

sails

	#include<bits/stdc++.h>

	using namespace std;
	
	vector<int> t, t2, L;

	inline void prop(int i, int s, int e){
		if(s != e){
			L[i*2] += L[i];
			L[i*2+1] += L[i];
		}
		t[i] += L[i];
		t2[i] += L[i];
		L[i] = 0;
	}

	void upd(int i, int s, int e, int l, int r){
		prop(i, s, e);
		if(l <= s && e <= r){
			L[i] += 1;
			prop(i, s, e);
			return;
		}
		if(s > r || e < l || s > e){
			return;
		}
		int m = (s + e)/2;
		upd(i*2, s, m, l, r);
		upd(i*2+1, m+1, e, l, r);
		t[i] = max(t[i*2], t[i*2+1]);
		t2[i] = min(t2[i*2], t2[i*2+1]);
	}

	int query(int i, int s, int e, int indx){
		prop(i, s, e);
		if(s == e) return t[i];
		int m = (s + e)/2;
		if(indx <= m) return query(i*2, s, m, indx);
		else return query(i*2+1, m+1, e, indx);
	}

	int right(int i, int s, int e, int l, int r, int val){
		prop(i, s, e);
		if(s > e || s > r || e < l) return -1;
		if(t[i] < val) return -1;
		if(l <= s && e <= r){  //completely inside
			if(s == e) return s;
		}
		int m = (s + e)/2;
		int ri = right(i*2+1, m+1, e, l, r, val);
		if(ri == -1) return right(i*2, s, m, l, r, val);
		else return ri;
	}

	int left(int i, int s, int e, int l, int r, int val){
		prop(i, s, e);
		if(s  > e || s > r || e < l) return -1;
		if(t2[i] > val) return -1;
		if(l <= s && e <= r){
			if(s == e) return s;
		}
		int m = (s + e)/2;
		int le = left(i*2, s, m, l, r, val);
		if(le != -1) return le;
		return left(i*2+1, m+1, e, l, r, val);
	}

	void print(int i, int s, int e){
		prop(i, s, e);
		if(s == e){
			cout<<"S: "<<t[i]<<endl;
			return;
		}
		int m = (s + e)/2;
		print(i*2, s, m);
		print(i*2+1, m+1, e);
	}

	signed main(){
		ios::sync_with_stdio(false); cin.tie(0);
		int N; cin>>N;
		vector<pair<int, int> > a(N);
		int n = 100;
		for(int i = 0; i < N; i++){
			cin>>a[i].first>>a[i].second;
			n = max(n, a[i].first);
		}
		sort(a.begin(), a.end());
				t = vector<int>(4*n, 0);
		t2 = vector<int>(4*n, 0);
		L = vector<int>(4*n, 0);

		for(int i = 0; i < N; i++){
			int h = a[i].first, k = a[i].second;
			//need to insert k masts in the end
			//cout<<"ADDING "<<h<<" "<<k<<endl;
			int v = query(1, 0, n-1, h-k);
			int l = left(1, 0, n-1, 0, h-1, v);
			int r = right(1, 0, n-1, 0, h-1, v);
			//cout<<v<<" "<<l<<" "<<r<<endl;
			if(r != h-1) upd(1, 0, n-1, r+1 ,h-1);
			upd(1, 0, n-1, l, l-1 + k-(h-r-1));
			//cout<<"UPDING FROM "<<l<<" "<<l-1 + (k-(h-r-1))<<" and "<<r+1<<" "<<h-1<<endl;
			//print(1, 0, n-1);
		}

		long long ans = 0;
		for(int i = 0; i < n; i++){
			long long v = query(1, 0, n-1, i);
			//cout<<i<<" : "<<v<<endl;
			ans = (ans + v*(v-1)/2);
		}
		cout<<ans<<endl;

	}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10