Submission #420057

#	Time	Username	Problem	Language	Result	Execution time	Memory
420057		errorgorn	Financial Report (JOI21_financial)	C++17	100 / 100	1416 ms	73332 KiB

Main

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

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,k;
int arr[300005];

vector<int> proc;

set<int> pos;

struct node1{
	int s,e,m;
	int val=0;
	node1 *l,*r;
	
	node1 (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node1(s,m);
			r=new node1(m+1,e);
		}
	}
	
	void update(int i,int j,int k){
		if (s==i && e==j) val=max(val,k);
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
		}
	}
	
	int query(int i){
		if (s==e) return val;
		else if (i<=m) return max(val,l->query(i));
		else return max(val,r->query(i));
	}
} *root=new node1(0,300005);

struct node2{
	int s,e,m;
	int val=0;
	node2 *l,*r;
	
	node2 (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node2(s,m);
			r=new node2(m+1,e);
		}
	}
	
	void update(int i,int k){
		if (s==e) val=k;
		else{
			if (i<=m) l->update(i,k);
			else r->update(i,k);
			
			val=max(l->val,r->val);
		}
	}
	
	int query(int i,int k){
		if (val<=k) return -1;
		if (s==e) return s;
		
		if (m<i) return r->query(i,k);
		else{
			int temp=l->query(i,k);
			if (temp==-1) return r->query(m+1,k);
			else return temp;
		}
	}
} *root2=new node2(0,300005);

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,0,n) cin>>arr[x];
	
	rep(x,0,n) proc.pub(x);
	
	sort(all(proc),[](int i,int j){
		if (arr[i]!=arr[j]) return arr[i]<arr[j];
		else return i>j;
	});
	
	pos.insert(1e9);
	
	for (auto &it:proc){
		ll temp=root->query(it)+1;
		auto iter=pos.insert(it).fi;
		
		if (iter!=pos.begin()){
			root2->update(*prev(iter),it-*prev(iter));
		}
		if (next(iter)!=pos.end()){
			root2->update(it,*next(iter)-it);
		}
		
		int hi=root2->query(it,k);
		
		//cout<<it<<" "<<hi<<" "<<temp<<endl;
		root->update(it,min(hi+k,300005),temp);
	}
	
	cout<<root->query(n-1)<<endl;
}

Compilation message (stderr)

Main.cpp: In constructor 'node1::node1(int, int)':
Main.cpp:36:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
Main.cpp: In constructor 'node2::node2(int, int)':
Main.cpp:66:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

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