제출 #387315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
387315		peijar	Sails (IOI07_sails)	C++17	100 / 100	113 ms	6716 KiB

sails

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