Submission #359584

#	Time	Username	Problem	Language	Result	Execution time	Memory
359584		alireza_kaviani	Sails (IOI07_sails)	C++17	100 / 100	223 ms	5608 KiB

sails

#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 (stderr)

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 / 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