Submission #886675

#	Time	Username	Problem	Language	Result	Execution time	Memory
886675		fanwen	Financial Report (JOI21_financial)	C++17	100 / 100	397 ms	22388 KiB

Main

/* author : bo may can 5 */

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); 

template < class T, T (*f) (T, T), T (*e) ()>
struct segment_tree {
    vector <T> it;
    int n;

    void update(int u, T p) {
        u--;
        for(it[u += n] += p; u >>= 1; ) {
            it[u] = f(it[u << 1], it[u << 1 | 1]);
        }
    }

    void set(int u, T p) {
        u--;
        for (it[u += n] = p; u >>= 1; ) {
            it[u] = f(it[u << 1], it[u << 1 | 1]);
        }
    }

    T get(int p) {
        return it[p += n - 1];
    }

    T get(int l, int r) {
        l--;
        T resl = e(), resr = e();
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) resl = f(resl, it[l++]);
            if(r & 1) resr = f(it[--r], resr);
        }
        return f(resl, resr);
    }

    segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
        fill(it.begin(), it.end(), T{});
    }
};

int op(int a, int b) { return a > b ? a : b; }
int e() { return 0; }

const int MAX = 3e5 + 5;

int n, D, dp[MAX];

pair <int, int> a[MAX];

set <int> s, diff;

void insert(int u) {
	s.insert(u);
	auto it = s.find(u);
	if(it != s.begin() && next(it) != s.end()) {
		if(*next(it) - *prev(it) > D) diff.erase(*next(it));
	}
	if(next(it) != s.end()) {
		int len = *next(it) - u;
		if(len > D) diff.insert(*next(it));
	}
	if(it != s.begin()) {
		int len = u - *prev(it);
		if(len > D) diff.insert(u);
	}
}

void you_make_it(void) {
    cin >> n >> D;
    for (int i = 1; i <= n; ++i) cin >> a[i].fi, a[i].se = i;
    sort(a + 1, a + n + 1, [&] (const pair <int, int> &x, const pair <int, int> &y) {
    	return x.fi < y.fi || (x.fi == y.fi && x.se > y.se);
    });

	segment_tree <int, op, e> it(n);
	int ans = 0, ptr = 1;
	for (int i = 1; i <= n; ++i) {
		while(ptr <= n && a[ptr].fi == a[i].fi) {
			insert(a[ptr++].se);
		}
		int d = 0, l = 0;
		auto iter = diff.upper_bound(a[i].se);
		if(iter == diff.begin()) l = 1;
		else l = *prev(iter);
		d = it.get(l, a[i].se - 1) + 1;
		// cout << l << " " << a[i].se << '\n';
		ans = max(ans, d);
		it.set(a[i].se, d);

	}
	cout << ans;
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("financial");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

Main.cpp: In instantiation of 'segment_tree<T, f, e>::segment_tree(int) [with T = int; T (* f)(T, T) = op; T (* e)() = e]':
Main.cpp:86:32:   required from here
Main.cpp:17:9: warning: 'segment_tree<int, op, e>::n' will be initialized after [-Wreorder]
   17 |     int n;
      |         ^
Main.cpp:16:16: warning:   'std::vector<int> segment_tree<int, op, e>::it' [-Wreorder]
   16 |     vector <T> it;
      |                ^~
Main.cpp:47:5: warning:   when initialized here [-Wreorder]
   47 |     segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
      |     ^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:5: note: in expansion of macro 'file'
  111 |     file("financial");
      |     ^~~~
Main.cpp:12:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:5: note: in expansion of macro 'file'
  111 |     file("financial");
      |     ^~~~

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