Submission #918008

#	Time	Username	Problem	Language	Result	Execution time	Memory
918008		waldi	Financial Report (JOI21_financial)	C++17	100 / 100	700 ms	93312 KiB

Main

#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int(x.size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

struct przedzialowiec{
	int N;
	vector<multiset<int>> sety;
	vector<int> t;
	przedzialowiec(int n){
		for(N = 1; N <= n;) N <<= 1;
		sety.resize(n+1);
		t.resize(N<<1, 0);
	}
	void napraw(int poz){
		t[poz+N-1] = sety[poz].empty() ? 0 : *prev(sety[poz].end());
		for(poz+=N-1; poz>>=1;) t[poz] = max(t[poz<<1], t[poz<<1|1]);
	}
	void dorzuc(int poz, int wart){
		sety[poz].emplace(wart);
		napraw(poz);
	}
	void wywal(int poz, int wart){
		sety[poz].erase(sety[poz].find(wart));
		napraw(poz);
	}
	int maks(int p, int k){
		int ret = 0;
		for(p+=N-1, k+=N; p<k; p>>=1, k>>=1){
			if(p&1) ret = max(ret, t[p++]);
			if(k&1) ret = max(ret, t[--k]);
		}
		return ret;
	}
};

int main(){
	int n, d;
	scanf("%d%d", &n, &d);
	set<int> wart;
	vector<int> wej(n+1);
	FOR(i, 1, n) scanf("%d", &wej[i]), wart.emplace(wej[i]);
	unordered_map<int, int> mapa;
	for(int it = 0; int x : wart) mapa[x] = ++it;
	FOR(i, 1, n) wej[i] = mapa[wej[i]];
	
	vector<vector<int>> kub(n+1);
	FOR(i, 1, n) kub[wej[i]].emplace_back(i);
	
	vector<int> prawo(n+1);
	set<int> duze_grupy;
	set<pii> grupy;
	for(int x = n+1; --x;){
		for(int i : kub[x]){
			auto it = duze_grupy.upper_bound(i);
			prawo[i] = it==duze_grupy.end() ? n : (*it)+d-1;
		}
		for(int i : kub[x]){
			int gdzie = i, ile = 1;
			auto it = grupy.lower_bound({i+1, 0});
			if(it != grupy.end() && it->fi == i+1){
				if(it->se >= d) duze_grupy.erase(it->fi);
				ile += it->se, it = grupy.erase(it);
			}
			if(it != grupy.begin() && prev(it)->fi + prev(it)->se == i){
				if(prev(it)->se >= d) duze_grupy.erase(prev(it)->fi);
				gdzie = prev(it)->fi, ile += prev(it)->se, grupy.erase(prev(it));
			}
			grupy.emplace(gdzie, ile);
			if(ile >= d) duze_grupy.emplace(gdzie);
		}
	}
	
	vector<int> dp(n+1, 0);
	przedzialowiec prz(n);
	vector<vector<pii>> akt(n+1);
	FOR(i, 1, n){
		dp[i] = 1 + prz.maks(1, wej[i]-1);
		prz.dorzuc(wej[i], dp[i]);
		akt[prawo[i]].emplace_back(wej[i], dp[i]);
		for(pii para : akt[i]) prz.wywal(para.fi, para.se);
	}
	
	int wyn = 0;
	FOR(i, 1, n) if(prawo[i] == n) wyn = max(wyn, dp[i]);
	printf("%d", wyn);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:49:18: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   49 |  for(int it = 0; int x : wart) mapa[x] = ++it;
      |                  ^~~
Main.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d%d", &n, &d);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:47:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  FOR(i, 1, n) scanf("%d", &wej[i]), wart.emplace(wej[i]);
      |               ~~~~~^~~~~~~~~~~~~~~

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