제출 #1309477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309477		Muhammad_Aneeq	3개의 봉우리 (IOI25_triples)	C++20	70 / 100	209 ms	16040 KiB

triples

#include <bits/stdc++.h>
using namespace std;
long long count_triples(vector<int> h)
{
	int n=h.size();
	int ans=0;
	for (int i=0;i<n;i++)
	{
		{//h[i] is maximum and i is starting point
			int k=i+h[i];
			if (k<n)
			{
				{// i,k-h[k],k
					int j=k-h[k];
					if  (j>i)
						if (h[j]==j-i)
							ans++;
				}
				{//i,i+h[k],k
					if (i+h[k]!=k-h[k])
					{
						int j=i+h[k];
						if (j<k)
							if (h[j]==k-j)
								ans++;
					}
				}
			}
		}
		{//h[i] is maximum and ending point
			int k=i-h[i];
			if (k>=0)
			{
				{// k,i-h[k],i
					int j=i-h[k];
					if  (j>k)
						if (h[j]==j-k)
							ans++;
				}
				{//k,k+h[k],i
					if (i-h[k]!=k+h[k])
					{
						int j=k+h[k];
						if (j<i)
							if (h[j]==i-j)
								ans++;
					}
				}
			}
		}
	}
	vector<int> vl[2*n+10]={};
	for (int i=n-1;i>=0;i--)//j-i==h[i]+h[j]    j-h[j]==i+h[i]
		vl[i-h[i]+n].push_back(i);
	for (int i=0;i<n;i++)
	{
		if (i+h[i]+n<=2*n)
		{
			for (auto k:vl[i+h[i]+n])
			{
				{//i i+h[k] k
					int j=i+h[k];
					if (j<k)
						if (h[j]==k-i)
							ans++;
				}
				{//i i+h[i] k
					int j=i+h[i];
					if (h[i]!=h[k]&&j<k)
						if (h[j]==k-i)
							ans++;
				}
			}
		}
		vl[i-h[i]+n].pop_back();	
	}
	return ans;
}
vector<int> construct_range(int M, int K)
{
	return {};
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 19
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5