oj.uz

Submission #129959

# Submission time Handle Problem Language Result Execution time Memory
129959 2019-07-13T16:00:40 Z Adhyyan1252 Sails (IOI07_sails) C++11
100 / 100
 329 ms 6036 KB 
	#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 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 6 ms 504 KB Output is correct
2 Correct 21 ms 5084 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1912 KB Output is correct
2 Correct 61 ms 888 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2172 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 3268 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 5808 KB Output is correct
2 Correct 227 ms 5752 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 5928 KB Output is correct
2 Correct 152 ms 5404 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 6036 KB Output is correct
2 Correct 207 ms 2748 KB Output is correct