oj.uz

Submission #129840

# Submission time Handle Problem Language Result Execution time Memory
129840 2019-07-13T10:28:02 Z Adhyyan1252 Sails (IOI07_sails) C++11
100 / 100
 383 ms 6904 KB 
	#include<bits/stdc++.h>

	using namespace std;

	
	vector<int> t, t2, L;

	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(l <= s && e <= r){  //completely inside
			if(t[i] < val) return -1;
			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(l <= s && e <= r){
			if(t2[i] > val) return -1;
			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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 28 ms 5240 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2012 KB Output is correct
2 Correct 73 ms 1144 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 2416 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 3576 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 6556 KB Output is correct
2 Correct 281 ms 6596 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 6836 KB Output is correct
2 Correct 165 ms 6136 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 6904 KB Output is correct
2 Correct 234 ms 3576 KB Output is correct