oj.uz

Submission #891296

# Submission time Handle Problem Language Result Execution time Memory
891296 2023-12-22T16:56:38 Z iris2617 Financial Report (JOI21_financial) C++14
0 / 100
 4000 ms 28612 KB 
#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
//const int iris = 1e9+7;
const int iris = 998244353;
using namespace std;

const int N=3e5;

struct sagiri
{
	vector<int> st;
	sagiri()
	{
		st.resize(N*4, 0);
	}
	void mdf(int i,int l,int r,int p,int x)
	{
		int m=l+(r-l)/2;
		if(l==r)
		{
			st[i]=x;
			return;
		}
		if(p<=m)
			mdf(i*2,l,m,p,x);
		else
			mdf(i*2+1,m+1,r,p,x);
		st[i]=max(st[i*2], st[i*2+1]);
	}
	int qry(int i,int l,int r,int L,int R)
	{
		int m=l+(r-l)/2;
		if(L<=l && r<=R)
			return st[i];
		else if(R<=m)
			return qry(i*2,l,m,L,R);
		else if(L>m)
			return qry(i*2+1,m+1,r,L,R);
		else
			return max(qry(i*2,l,m,L,r), qry(i*2+1,m+1,r,L,R) );
	}
}dis, dp;

void solve()
{
	int n,d;
	cin>>n>>d;
	vector<matsuri> arr;
	for(int i=1;i<=n;i++)
	{
		int a;
		cin>>a;
		arr.emplace_back(a,-i);
	}
	sort(arr.begin(), arr.end());
	set<int> s;
	
	dp.mdf(1,0,n,0,0);
	s.insert(0);
	dis.mdf(1,0,n,0,n);
	
	int ii=0;
	for(auto [a,i]:arr)
	{
		i*=-1;
		while(ii<n && arr[ii].first==a)
		{
			//cout<<ii<<'\n';
			int j=arr[ii++].second*-1;
			s.insert(j);
			auto it=s.find(j);
			it--;
			dis.mdf(1,0,n,*it,j-*it);
			//cout<<" . "<<*it<<' '<<j<<'\n';
			it=upper_bound(s.begin(), s.end(), a);
			if(it==s.end())
				dis.mdf(1,0,n,j,n-j);
			else
				dis.mdf(1,0,n,j,*it-j);
		}
		
		int l=0, r=i;
		//cout<<i<<' '<<a<<'\n';
		while(l<r)
		{
			int m=l+(r-l)/2;
			//cout<<" - "<<m<<' '<<dis.qry(1,0,n,m,i-1)<<'\n';
			//for(int j=m;j<=i;j++)
			//	cout<<"     "<<dis.qry(1,0,n,j,j)<<'\n';
			if(dis.qry(1,0,n,m,i-1)<=d)
				r=m;
			else
				l=m+1;
		}
		//cout<<' '<<l<<' '<<i<<' '<<dp.qry(1,0,n,l,i)<<'\n';
		dp.mdf(1,0,n,i,dp.qry(1,0,n,l,i)+1);
	}
	cout<<dp.qry(1,0,n,0,n)<<'\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	
	int T=1;
	//cin>>T;
	while(T--)
		solve();
	
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:64:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |  for(auto [a,i]:arr)
      |           ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19288 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 5 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19184 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 5 ms 19036 KB Output is correct
12 Correct 4 ms 19036 KB Output is correct
13 Correct 4 ms 19036 KB Output is correct
14 Correct 4 ms 19036 KB Output is correct
15 Incorrect 4 ms 19036 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19288 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 5 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19184 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 5 ms 19036 KB Output is correct
12 Correct 4 ms 19036 KB Output is correct
13 Correct 4 ms 19036 KB Output is correct
14 Correct 4 ms 19036 KB Output is correct
15 Incorrect 4 ms 19036 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19288 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 5 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19184 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 5 ms 19036 KB Output is correct
12 Correct 4 ms 19036 KB Output is correct
13 Correct 4 ms 19036 KB Output is correct
14 Correct 4 ms 19036 KB Output is correct
15 Incorrect 4 ms 19036 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4009 ms 28612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4033 ms 27592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 19288 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 5 ms 19036 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19184 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 5 ms 19036 KB Output is correct
12 Correct 4 ms 19036 KB Output is correct
13 Correct 4 ms 19036 KB Output is correct
14 Correct 4 ms 19036 KB Output is correct
15 Incorrect 4 ms 19036 KB Output isn't correct
16 Halted 0 ms 0 KB -