Submission #520287

#	Time	Username	Problem	Language	Result	Execution time	Memory
520287		CPSC	Financial Report (JOI21_financial)	C++14	100 / 100	650 ms	40512 KiB

Main

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5;
int t,n,a[N],p[N],pas,ans,d,par,tree[4*N],idx,idx1,val;
multiset <int> ms,ms1;
multiset <int> :: iterator it;
vector <pii > v;
int get_col(int a) {
    if (a == p[a]) return a;
    else return p[a] = get_col(p[a]);
}
void col(int a, int b) {
    a = get_col(a);
    b = get_col(b);
    if (a == b) return ;
    if (a > b) swap(a,b);
    p[b] = a;
}
void update(int node, int le, int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        tree[node] = val;
        return ;
    }
    int mid = (le + ri) / 2;
    update(2*node,le,mid,idx,val);
    update(2*node + 1, mid + 1, ri, idx, val);
    tree[node] = max(tree[2*node], tree[2 * node + 1]);
}
int getans(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return 0;
    if (le >= start && ri <= end) 
        return tree[node];
    int mid = (le + ri) / 2;
    return max(getans(2*node,le,mid,start,end), getans(2*node + 1, mid + 1, ri, start,end));
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>d;
	for(int i = 1; i <= n; i++) {
	    cin>>a[i];
	    v.pb({a[i],-i});
	}
	sort(v.begin(),v.end());
	for (int i = 0; i < v.size(); i++){
	    a[-v[i].s] = i + 1;
	}
	v.clear();
	for (int i = 1; i <= n; i++) {
	    v.pb({a[i],i});
	}
	sort(v.begin(),v.end());
	for (int i = 1; i <= n; i++) {
	    p[i] = i;
	}
	for (int i = 0; i < v.size(); i++) {
	    val = v[i].f; idx = v[i].s;
	    it = ms.upper_bound(idx);
	    if (it != ms.end()) {
	        idx1 = *it;
	        if (idx1 - d <= idx) col(idx,idx1);
	    }
	    it = ms1.upper_bound(-idx);
	    if (it != ms1.end()) {
	        idx1 = -(*it);
	        if (idx - d <= idx1) col(idx1,idx);
	    }
	    par = get_col(idx);
	    pas = getans(1,1,n,par,idx - 1) + 1;
	    update(1,1,n,idx,pas);
	    ans = max(ans,pas);
	    ms.insert(idx); ms1.insert(-idx);
	}
	cout<<ans<<"\n";
}

Compilation message (stderr)

Main.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 0; i < v.size(); i++){
      |                  ~~^~~~~~~~~~
Main.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for (int i = 0; i < v.size(); 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