oj.uz

Submission #359584

# Submission time Handle Problem Language Result Execution time Memory
359584 2021-01-27T05:06:16 Z alireza_kaviani Sails (IOI07_sails) C++17
100 / 100
 223 ms 5608 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())
#define lc							id << 1
#define rc							lc | 1

const ll MAXN = 1e5 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , lz[MAXN << 2] , mx[MAXN << 2] , mn[MAXN << 2];
ll ans;
vector<pii> vec;

void shift(int id){
	lz[lc] += lz[id]; lz[rc] += lz[id];
	mn[lc] += lz[id]; mn[rc] += lz[id];
	mx[lc] += lz[id]; mx[rc] += lz[id];
	lz[id] = 0;
}

void update(int ql , int qr , int id = 1 , int l = 0 , int r = MAXN){
	if(qr <= l || r <= ql)	return;
	if(ql <= l && r <= qr){
		lz[id]++; mx[id]++; mn[id]++;
		return;
	}
	shift(id);
	int mid = l + r >> 1;
	update(ql , qr , lc , l , mid);
	update(ql , qr , rc , mid , r);
	mx[id] = mx[lc]; mn[id] = mn[rc];
}

int get(int x , int id = 1 , int l = 0 , int r = MAXN){
	if(r - l == 1)	return mx[id];
	shift(id);
	int mid = l + r >> 1;
	if(x < mid)	return get(x , lc , l , mid);
	return get(x , rc , mid , r);
}

pii find(int x , int id = 1 , int l = 0 , int r = MAXN){
	if(mn[id] > x || mx[id] < x)	return {MOD , -MOD};
	if(mx[id] == mn[id])	return {l , r};
	shift(id);
	int mid = l + r >> 1;
	pii A = find(x , lc , l , mid);
	pii B = find(x , rc , mid , r);
	return {min(A.X , B.X) , max(A.Y , B.Y)};
}

void calc(int id = 1 , int l = 0 , int r = MAXN){
	if(r - l == 1){
		ans += 1ll * mx[id] * (mx[id] - 1) / 2;
		return;
	}
	shift(id);
	int mid = l + r >> 1;
	calc(lc , l , mid);
	calc(rc , mid , r);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n;
	for(int i = 0 ; i < n ; i++){
		int h , k;
		cin >> h >> k;
		vec.push_back({h , k});
	}
	sort(all(vec));
	for(pii i : vec){
		int h = i.X , k = i.Y;
		int x = get(h - k);
		pii A = find(x);
		int l = A.X , r = min(h , A.Y);
		//cout << l << sep << r << endl;
		update(r , h);
		update(l , l + k - h + r);
	}
	calc();
	cout << ans << endl;

    return 0;
}
/*

*/

Compilation message

sails.cpp: In function 'void update(int, int, int, int, int)':
sails.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int mid = l + r >> 1;
      |            ~~^~~
sails.cpp: In function 'int get(int, int, int, int)':
sails.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int mid = l + r >> 1;
      |            ~~^~~
sails.cpp: In function 'pii find(int, int, int, int)':
sails.cpp:58:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |  int mid = l + r >> 1;
      |            ~~^~~
sails.cpp: In function 'void calc(int, int, int)':
sails.cpp:70:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3436 KB Output is correct
2 Correct 5 ms 3436 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3692 KB Output is correct
2 Correct 52 ms 4080 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4080 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 4580 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 4968 KB Output is correct
2 Correct 151 ms 5096 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 5352 KB Output is correct
2 Correct 125 ms 4968 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 5608 KB Output is correct
2 Correct 164 ms 5352 KB Output is correct