oj.uz

Submission #119047

# Submission time Handle Problem Language Result Execution time Memory
119047 2019-06-20T08:21:58 Z nvmdava Sails (IOI07_sails) C++17
100 / 100
 325 ms 3824 KB 
#include <bits/stdc++.h>
using namespace std;

int tree[100005], lazy[400005];
vector<pair<int, int> > v;

void update(int id, int l, int r, int L, int R){
	if(l == L && r == R){
		lazy[id]++;
		return;
	}
	int m = (l + r) >> 1;
	if(m < L) update(id << 1 | 1, m + 1, r, L, R);
	else if(m >= R) update(id << 1, l, m, L, R);
	else {
		update(id << 1, l, m, L, m);
		update(id << 1 | 1, m + 1, r, m + 1, R);
	}
}
void push(int id, int l, int r){
	if(l == r) tree[l] += lazy[id];
	else {
		lazy[id << 1] += lazy[id];
		lazy[id << 1 | 1] += lazy[id];
	}
	lazy[id] = 0;
}

int query(int id, int l, int r, int x){
	push(id, l, r);
	if(l == r) return tree[l];
	int m = (l + r) >> 1;
	if(m < x) return query(id << 1 | 1, m + 1, r, x);
	return query(id << 1, l, m, x);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	
	for(int i = 1; i <= n; i++){
		int h, k;
		cin>>h>>k;
		v.push_back({h, k});
	}
	sort(v.begin(), v.end());
	for(auto& x : v){
		int h = x.first;
		int k = x.second;
		int idr = h - k + 1;
		int idl = idr;
		int val = query(1, 1, 100000, idr);
		for(int j = 19; j >= 0; j--){
			if(idl - (1 << j) > 0 && query(1, 1, 100000, idl - (1 << j)) == val) idl -= (1 << j);
			if(idr + (1 << j) <= h && query(1, 1, 100000, idr + (1 << j)) == val) idr += (1 << j);
		}
		int ri = h - idr;
		int le = k - ri;
		if(le) update(1, 1, 100000, idl, idl + le - 1);
		if(ri) update(1, 1, 100000, idr + 1, idr + ri);
	}
	long long res = 0;
	for(int i = 1; i <= 100000; i++){
		long long a = query(1, 1, 100000, i);
		res += a * (a - 1) / 2;
	}
	cout<<res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1920 KB Output is correct
2 Correct 9 ms 1792 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1792 KB Output is correct
2 Correct 9 ms 1792 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1792 KB Output is correct
2 Correct 10 ms 1764 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1792 KB Output is correct
2 Correct 14 ms 1792 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1912 KB Output is correct
2 Correct 66 ms 2424 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2128 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2248 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 2560 KB Output is correct
2 Correct 203 ms 3440 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 2596 KB Output is correct
2 Correct 114 ms 3308 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 2816 KB Output is correct
2 Correct 183 ms 3824 KB Output is correct