oj.uz

Submission #880669

# Submission time Handle Problem Language Result Execution time Memory
880669 2023-11-29T20:00:18 Z BBart888 Sails (IOI07_sails) C++14
0 / 100
 905 ms 4416 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 = 1e5 + 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;
int h[MAXN];
int k[MAXN];
int lazy[4 * MAXN];
int t[4 * MAXN];
ll ans;

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, int 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]);
	}
}

int 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 >> h[i] >> k[i];
	}


	for (int i = n; i >= 1; i--)
	{
		int last_mast = h[i] - k[i] + 1;
		int ele = query(1, 0, MAXN, last_mast, last_mast);
		
		int L = last_element(ele, h[i]);
		int F = first_element(ele, h[i]);

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


	}

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

	cout<<ans<<'\n';




	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 2536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 231 ms 2976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 416 ms 3244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 727 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 850 ms 4244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 905 ms 4416 KB Output isn't correct
2 Halted 0 ms 0 KB -