oj.uz

Submission #387315

# Submission time Handle Problem Language Result Execution time Memory
387315 2021-04-08T09:04:31 Z peijar Sails (IOI07_sails) C++17
100 / 100
 113 ms 6716 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Fenwick
{
	int N;
	vector<int> bit;

	Fenwick(int n) : N(n+1), bit(N) {}

	void upd(int pos, int add)
	{
		for (pos++; pos < N; pos += pos & -pos)
			bit[pos] += add;
	}

	int query(int r) // < r
	{
		int ret(0);
		for (; r; r -= r & -r)
		{
			ret += bit[r];
		}
		return ret;
	}

	void updRange(int l, int r, int add) // [l, r)
	{
		upd(l, add); upd(r, -add);
	}

	int queryPoint(int pos)
	{
		return query(pos+1);
	}

	int nbPlusPetit(int val, int nbElem) // nb <
	{
		if (queryPoint(nbElem-1) >= val) return 0;
		int lo(1), up(nbElem);
		while (lo < up)
		{
			int mil = (lo + up + 1) / 2;
			if (queryPoint(nbElem - mil) < val)
				lo = mil;
			else
				up = mil-1;
		}
		return lo;
	}
};

const int MAXN = 1e5+1;

vector<int> aHauteur[MAXN];
Fenwick fen(MAXN);

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbPoteaux;
	cin >> nbPoteaux;
	for (int iPoteau = 0; iPoteau < nbPoteaux; ++iPoteau) 
	{
		int hauteur, aMettre;
		cin >> hauteur >> aMettre;
		aHauteur[hauteur].push_back(aMettre);
	}

	for (int hauteur(1); hauteur < MAXN; ++hauteur)
		for (auto aMettre : aHauteur[hauteur])
		{
			int valPlusGrand = fen.queryPoint(hauteur - aMettre);
			int posDernierGrand = hauteur - 1 -fen.nbPlusPetit(valPlusGrand, hauteur);
			int posPremierGrand = hauteur - fen.nbPlusPetit(valPlusGrand+1, hauteur);
			fen.updRange(posDernierGrand+1, hauteur, 1);
			fen.updRange(posPremierGrand, posPremierGrand + (aMettre - (hauteur - posDernierGrand-1)), 1);
		}
	int ret(0);
	for (int h(0); h < MAXN; ++h)
	{
		int nbAH = fen.queryPoint(h);
		ret += nbAH * (nbAH-1) / 2;
	}
	cout << ret << endl;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3692 KB Output is correct
2 Correct 25 ms 4204 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4768 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5100 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 5484 KB Output is correct
2 Correct 72 ms 5992 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6508 KB Output is correct
2 Correct 52 ms 5356 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 6716 KB Output is correct
2 Correct 62 ms 5568 KB Output is correct