oj.uz

답안 #587676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
587676 2022-07-02T08:16:55 Z LittlePants Meteors (POI11_met) C++17
74 / 100
 560 ms 60276 KB 
#define ll loli
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define push emplace
#define lb(x, v) lower_bound(all(x), v)
#define ub(x, v) upper_bound(all(x), v)
#define sz(x) (int)(x.size())
#define re(x) reverse(all(x))
#define uni(x) x.resize(unique(all(x)) - x.begin())
#define all(x) x.begin(), x.end()
#define mem(x, v) memset(x, v, sizeof x); 
#define int long long
#define pii pair<int, int>
#define inf 1000000000
#define INF 1000000000000000000
#define mod 1000000007
#define F first
#define S second
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
#define chmax(a, b) (a = (b > a ? b : a))
#define chmin(a, b) (a = (b < a ? b : a))
#define get_bit(x, y) ((x>>y)&1)
#define mkp make_pair
using namespace std;

#ifdef loli
void trace_() {cerr << "\n";}
template<typename T1, typename... T2> void trace_(T1 t1, T2... t2) {cerr << ' ' << t1; trace_(t2...); }
#define trace(...) cerr << "[" << #__VA_ARGS__ << "] :", trace_(__VA_ARGS__);
#else
#define trace(...) 49
#endif

const int mxN = 3e5 + 5;

int n, m, k, a[mxN], ans[mxN];

int tot;
array<int, 3> v[mxN * 5], tmp[mxN * 5];
bool cmp(array<int, 3> a, array<int, 3> b) {
	if (a[1] == b[1]) return (a[0] == 0 ? INF : a[0]) < (b[0] == 0 ? INF : b[0]);
	return a[1] < b[1];
}

void bs(int l, int r, int ql, int qr) {
	if (l == r) {
		for (int j = ql; j <= qr; j++) {
			auto [i, p, o] = v[j];
			if (!i) ans[o] = l;
		}
		return;
	}
	int mid = (l + r) >> 1, res = 0;

	for (int j = ql; j <= qr; j++) {
		auto [i, x, val] = v[j];
		if (i and i <= mid) res += val;
		if (!i) a[val] -= res;
	}

	int tl = ql, tr = qr;
	for (int j = ql; j <= qr; j++) {
		auto [i, x, val] = v[j];
		if (i) {
			if (i <= mid) tmp[tl++] = v[j];
			else tmp[tr--] = v[j];
		} else {
			if (a[val] <= 0) tmp[tl++] = v[j];
			else tmp[tr--] = v[j];
		}
	}
	reverse(tmp + tl, tmp + qr + 1);
	copy(tmp + ql, tmp + qr + 1, v + ql);

	res = 0;
	for (int j = ql; j < tl; j++) {
		auto [i, x, val] = v[j];
		if (i)  res += val;
		else a[val] += res;
	}

	bs(l, mid, ql, tr);
	bs(mid+1, r, tl, qr);
}

inline void solve() {
	cin >> n >> m;
	vector<int> o(m + 1);
	for (int i = 1; i <= m; i++) cin >> o[i];
	for (int i = 1; i <= n; i++) cin >> a[i];

	for (int i = 1; i <= m; i++) {
		v[tot++] = {0, i, o[i]};
	}

	cin >> k;
	for (int i = 1; i <= k; i++) {
		int l, r, x; cin >> l >> r >> x;
		if (l > r) {
			v[tot++] = {i, l, x};
			v[tot++] = {i, 1, x};
			v[tot++] = {i, r + 1, -x};
		} else {
			v[tot++] = {i, l, x};
			if (r + 1 <= m) v[tot++] = {i, r + 1, -x};
		}
	}

	sort(v, v + tot, cmp);
	bs(1, k + 1, 0, tot - 1);

	for (int i = 1; i <= n; i++) {
		if (ans[i] == 0 or ans[i] == k + 1) cout << "NIE\n";
		else cout << ans[i] << '\n';
	}
}

signed main() {
	IO;	
	solve();	
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 7756 KB Output is correct
2 Correct 72 ms 10008 KB Output is correct
3 Correct 79 ms 8292 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 9148 KB Output is correct
2 Correct 76 ms 9140 KB Output is correct
3 Correct 78 ms 9932 KB Output is correct
4 Correct 20 ms 3768 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 7740 KB Output is correct
2 Correct 57 ms 10544 KB Output is correct
3 Correct 52 ms 6228 KB Output is correct
4 Correct 83 ms 8360 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 9556 KB Output is correct
2 Correct 86 ms 9708 KB Output is correct
3 Correct 64 ms 8064 KB Output is correct
4 Correct 93 ms 9416 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 508 ms 54208 KB Output is correct
2 Incorrect 375 ms 60276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 560 ms 53908 KB Output is correct
2 Incorrect 281 ms 44876 KB Output isn't correct
3 Halted 0 ms 0 KB -