Submission #1243918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243918		lovrot	Financial Report (JOI21_financial)	C++20	0 / 100	1656 ms	42200 KiB

Main

#include <cstdio>
#include <algorithm>
#include <vector>

#define db(...) //fprintf(stderr, __VA_ARGS__)
#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int LOG = 19;
const int N = 1 << LOG;

struct node { 
	int axi = 0, prf = 0, suf = 0, siz = 0;
	node() {}
};

node T1[2 * N];

node merge(node a, node b) { 
	node c;
	c.siz = a.siz + b.siz;
	c.axi = max(max(a.axi, b.axi), a.suf + b.prf);
	c.prf = a.prf + (a.prf == a.siz ? b.prf : 0);
	c.suf = b.suf + (b.suf == b.siz ? a.suf : 0);
	return c;
}

void upali(int x) { 
	x += N;
	T1[x].axi = T1[x].suf = T1[x].prf = 1;
	for(x >>= 1; x; x >>= 1) { 
		T1[x] = merge(T1[2 * x], T1[2 * x + 1]);
	}
}

node segment(int l, int r, int x = 1, int lo = 0, int hi = N) {
	if(r <= lo || hi <= l) { return node(); }
	if(l <= lo && hi <= r) { return T1[x]; }
	int mi = (lo + hi) / 2;
	return merge(segment(l, r, 2 * x, lo, mi), segment(l, r, 2 * x + 1, mi, hi));
}

int T2[2 * N];

void update(int x, int val) { 
	x += N;
	T2[x] = val;
	for(x >>= 1; x; x >>= 1) {
		T2[x] = max(T2[2 * x], T2[2 * x + 1]);
	}
}

int query(int l, int r, int x = 1, int lo = 0, int hi = N) { 
	if(r <= lo || hi <= l) { return 0; }
	if(l <= lo && hi <= r) { return T2[x]; }
	int mi = (lo + hi) / 2;
	return max(query(l, r, 2 * x, lo, mi), query(l, r, 2 * x + 1, mi, hi));
}

int A[N], ind[N], p[N], od[N], dp[N];
vector<int> ugasi[N];

int main() { 
	for(int i = N; i < 2 * N; ++i) { T1[i].siz = 1; }
	for(int i = N - 1; i; --i) { T1[i].siz = T1[2 * i].siz + T1[2 * i + 1].siz; }

	int n, d;
	scanf("%d%d", &n, &d);
	for(int i = 1; i <= n; ++i) { 
		scanf("%d", A + i);
		ind[i] = i;
	}

	sort(ind + 1, ind + n + 1, [](int a, int b) { 
		return A[a] > A[b] || (A[a] == A[b] && a > b);
	});

	A[0] = -1;
	for(int i = 1; i <= n; ++i) { 
		int x = ind[i];
		p[x] = i;
		if(A[x] != A[ind[i - 1]]) { od[x] = i - 1; }
		else { od[x] = od[ind[i - 1]]; }


		int lo = -1, hi = x;
		for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) { 
			if(segment(mi, x).axi >= d) { lo = mi; }
			else { hi = mi; }
		}
		db("%d %d(%d) %d, -> %d\n", i, x, A[x], od[x], hi);
		ugasi[hi].PB(p[x]);
		upali(x);
	}

	int ans = 0;
	for(int i = n - 1; i >= 0; --i) { 
		dp[i] = 1 + query(1, od[i] + 1);
		update(p[i], dp[i]);
		for(int x : ugasi[i]) { update(x, 0); }
		ans = max(ans, dp[i]);
	}
	
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d%d", &n, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:76:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |                 scanf("%d", A + i);
      |                 ~~~~~^~~~~~~~~~~~~

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