oj.uz

Submission #880673

# Submission time Handle Problem Language Result Execution time Memory
880673 2023-11-29T20:10:33 Z BBart888 Sails (IOI07_sails) C++14
100 / 100
 894 ms 12388 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11100 KB Output is correct
2 Correct 28 ms 11248 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11088 KB Output is correct
2 Correct 29 ms 11072 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11096 KB Output is correct
2 Correct 37 ms 11092 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11064 KB Output is correct
2 Correct 30 ms 11088 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 11092 KB Output is correct
2 Correct 41 ms 11352 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11224 KB Output is correct
2 Correct 191 ms 11600 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 11836 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 11760 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 11960 KB Output is correct
2 Correct 690 ms 12280 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 12224 KB Output is correct
2 Correct 677 ms 12116 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 12100 KB Output is correct
2 Correct 656 ms 12388 KB Output is correct