제출 #1310585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310585		miniob	Financial Report (JOI21_financial)	C++20	100 / 100	357 ms	24080 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int drz[1048576];
int a[300007];
int minnd[300007];
int dp[300007];

void ustaw(int gdzie, int co)
{
	gdzie += 524288;
	drz[gdzie] = co;
	gdzie /= 2;
	while(gdzie != 0)
	{
		drz[gdzie] = max(drz[2 * gdzie], drz[2 * gdzie + 1]);
		gdzie /= 2;
	}
}

int maxx(int l, int r, int curl, int curr, int cur)
{
	if(l > curr || r < curl)
	{
		return 0;
	}
	else if(l <= curl && curr <= r)
	{
		return drz[cur];
	}
	else
	{
		return max(maxx(l, r, curl, (curl + curr) / 2, 2 * cur), maxx(l, r, (curl + curr) / 2 + 1, curr, 2 * cur + 1));
	}
}

bool sfunkc(int x, int y)
{	
	if(a[x] != a[y])
	{
		return a[x] > a[y];
	}
	return x < y;
}

bool sfunkc2(pair<int, int> x, pair<int, int> y)
{	
	if(x.first != y.first)
	{
		return x.first > y.first;
	}
	return x.second < y.second;
}

int main() 
{
	int n, d;
	cin >> n >> d;
	vector<int> kolej;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		kolej.push_back(i);
	}
	sort(kolej.begin(), kolej.end(), sfunkc);
    deque<int> q;
    for (int i = 1; i <= n; i++) 
    {
        while (!q.empty() && a[q.back()] >= a[i])
        {
        	q.pop_back();
        }
        q.push_back(i);
        while (!q.empty() && q.front() <= i - d)
        {
        	q.pop_front();
        }
        if (i >= d)
        {
        	minnd[i] = a[q.front()];
        }
    }
    vector<pair<int, int>> eventy;
    for(int i = d; i <= n; i++)
    {
    	eventy.push_back({minnd[i], i});
    }
    sort(eventy.begin(), eventy.end(), sfunkc2);
    /*for(auto x : eventy)
	{
		cout << x.first << " " << x.second << endl;
	}*/
	int iter = 0, iter2 = 0, iter3 = 0;
	set<int> mniejsze;
	while(iter < n)
	{
		while(iter3 < n && a[kolej[iter]] == a[kolej[iter3]])
		{
			iter3++;
		}
		while(iter2 < eventy.size() && eventy[iter2].first > a[kolej[iter]])
		{
			mniejsze.insert(eventy[iter2].second);
			iter2++;
		}
		for(int i = iter; i < iter3; i++)
		{
			int ile;
			if(kolej[i] + d <= n)
			{
				auto it = mniejsze.lower_bound(kolej[i] + d);
				if(it == mniejsze.end())
				{
					ile = n;
				}
				else
				{
					ile = *it;
				}
			}
			else
			{
				ile = n;
			}
			dp[kolej[i]] = maxx(kolej[i], ile - 1, 0, 524287, 1) + 1;
		}
		for(int i = iter; i < iter3; i++)
		{
			ustaw(kolej[i] - 1, dp[kolej[i]]);
		}
		iter = iter3;
	}
	cout << maxx(0, n - 1, 0, 524287, 1) << endl;
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35