oj.uz

답안 #763208

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763208 2023-06-22T06:44:54 Z CDuong Financial Report (JOI21_financial) C++17
5 / 100
 164 ms 13476 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
using namespace std;

const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

vii v;
int n, d, a[mxN];
int segtree[4 * mxN], lazy[4 * mxN];

void down(int idx) {
	int val = lazy[idx];

	segtree[idx << 1] = max(segtree[idx << 1], val);
	lazy[idx << 1] = max(lazy[idx << 1], val);

	segtree[idx << 1 | 1] = max(segtree[idx << 1 | 1], val);
	lazy[idx << 1 | 1] = max(lazy[idx << 1 | 1], val);

	lazy[idx] = 0;
}

void update(int l, int r, int idx, int u, int v, int val) {
	if(r < u || v < l || r < l) return;
	if(u <= l && r <= v) {
		segtree[idx] = max(segtree[idx], val);
		lazy[idx] = max(lazy[idx], val);
		return;
	}

	down(idx);

	int mid = (l + r) >> 1;
	update(l, mid, idx << 1, u, v, val);
	update(mid + 1, r, idx << 1 | 1, u, v, val);

	segtree[idx] = max(segtree[idx << 1], segtree[idx << 1 | 1]);
}

int get(int l, int r, int idx, int pos) {
	if(l == r) {
		return segtree[idx];
	}

	down(idx);

	int mid = (l + r) >> 1;
	if(pos <= mid) return get(l, mid, idx << 1, pos);
	return get(mid + 1, r, idx << 1 | 1, pos);
}

void solve() {
	cin >> n >> d;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		v.emplace_back(a[i], i);
	}
	sort(all(v), [&](pii x, pii y) {
		if(x.ff == y.ff) return (x.ss > y.ss);
		return (x.ff < y.ff);
	});
	for(pii &tmp : v) {
		int cur = get(1, n, 1, tmp.ss) + 1;
		update(1, n, 1, tmp.ss, min(n, tmp.ss + d), cur);
	}
	cout << get(1, n, 1, n) << endl;
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1; //cin >> t;
	while(t--) solve();

#ifdef CDuongg
	auto end = chrono::high_resolution_clock::now();
	cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
	cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 12072 KB Output is correct
2 Incorrect 142 ms 12188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 12124 KB Output is correct
2 Correct 151 ms 12172 KB Output is correct
3 Correct 164 ms 12192 KB Output is correct
4 Correct 164 ms 12184 KB Output is correct
5 Correct 157 ms 12096 KB Output is correct
6 Correct 162 ms 12192 KB Output is correct
7 Correct 128 ms 12072 KB Output is correct
8 Correct 116 ms 13368 KB Output is correct
9 Correct 136 ms 13476 KB Output is correct
10 Correct 151 ms 13420 KB Output is correct
11 Correct 163 ms 13448 KB Output is correct
12 Correct 155 ms 13368 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -