Submission #880673

#	Time	Username	Problem	Language	Result	Execution time	Memory
880673		BBart888	Sails (IOI07_sails)	C++14	100 / 100	894 ms	12388 KiB

sails

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"



using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;



const int INF = 2147483640;
const int MAXN = 2e5 + 111;
const int MAXS = 1e5 + 111;
const long long P = 31;
using ll = long long;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;



int n;

ll lazy[4 * MAXN];
ll t[4 * MAXN];
ll ans;
pair<int, int> arr[MAXN];

ll get_sum(ll N)
{
	return (N * (N + 1)) / 2;
}

void push(int v) {
	t[v * 2] += lazy[v];
	lazy[v * 2] += lazy[v];
	t[v * 2 + 1] += lazy[v];
	lazy[v * 2 + 1] += lazy[v];
	lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, ll addend) {
	if (l > r)
		return;
	if (l == tl && tr == r) {
		t[v] += addend;
		lazy[v] += addend;
	}
	else {
		push(v);
		int tm = (tl + tr) / 2;
		update(v * 2, tl, tm, l, min(r, tm), addend);
		update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, addend);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
}

ll query(int v, int tl, int tr, int l, int r) {
	if (l > r)
		return -INF;
	if (l == tl && tr == r)
		return t[v];
	push(v);
	int tm = (tl + tr) / 2;
	return max(query(v * 2, tl, tm, l, min(r, tm)),
		query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}

int first_element(int x,int lim)
{
	int l = 1, r = lim;

	while (l < r)
	{
		int m = (l + r + 1) / 2;
		if (query(1, 0, MAXN, m, lim) >= x)
			l = m;
		else
			r = m - 1;
	}

	return l;
}


int last_element(int x,int lim)
{
	int l = 1, r = lim;
	while (l < r)
	{
		int m = (l + r) / 2;
		if (query(1, 0, MAXN, m, lim) > x)
			l = m + 1;
		else
			r = m;
	}
	return l;
}



int main() {

	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);

	
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i].first >> arr[i].second;
	}

	sort(arr + 1, arr + 1 + n);

	for (int i = 1; i <= n; i++)
	{
		int H = arr[i].first;
		int K = arr[i].second;

		int last_mast = H - K + 1;
		int ele = query(1, 0, MAXN, last_mast, last_mast);
		
		int L = last_element(ele, H);
		int F = first_element(ele, H);

		if (L == last_mast)
		{
			update(1, 0, MAXN, last_mast, H, 1);
		}
		else
		{
			//cout << F << " " << L << " " << ele << " XX " << k[i] << '\n';
			update(1, 0, MAXN, F + 1, H, 1);
			int rest = K - (H - (F + 1) + 1);
			update(1, 0, MAXN, L, L + rest - 1, 1);
		}


	}

	for (int i = 1; i <= (int)2e5; i++)
	{
		ans += get_sum(max(0ll,query(1, 0, MAXN, i, i)-1));
	}

	cout<<ans<<'\n';




	return 0;
}

• 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