답안 #942528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942528	2024-03-10T19:46:29 Z	Clan328	Meteors (POI11_met)	C++17	74 / 100	3205 ms	65536 KB

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll MOD = 1e9 + 7;

void settings()__attribute__((constructor));

// void eval(bool condition) { cout << (condition ? "yes" : "no") << nL; }
// void Eval(bool condition) { cout << (condition ? "Yes" : "No") << nL; }
// void EVAL(bool condition) { cout << (condition ? "YES" : "NO") << nL; }

int ipow(int a, int n) {
   if (n == 0) return 1;
   int x = ipow(a, n/2);
   if (n % 2 == 0) return x*x;
   return x*x*a;
}

template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
	for (auto elem : v) 
		stream << elem << " ";
	return stream;
}

template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
   for(auto &elem : v)
		stream >> elem;
   return stream;
}

void settings() {
	#ifdef LOCAL
		freopen("io/input.txt", "r", stdin);
		freopen("io/output.txt", "w", stdout);
	#endif

	ios::sync_with_stdio(0);
	cin.tie(0);
}

struct Rain {
	int l, r;
	ll a;
};

int LOG = 25;

struct SegmentTree {
	vl t;

	SegmentTree(int n) {
		t = vl(2*n);
	}

	void update(int v, int tl, int tr, int l, int r, ll x) {
		if (l > r) return;
		if (l == tl && r == tr) {
			t[v] += x;
			return;
		}

		int tm = (tl+tr)/2;

		update(v+1, tl, tm, l, min(r, tm), x);
		update(v+2*(tm-tl+1), tm+1, tr, max(tm+1, l), r, x);
	}

	ll get(int v, int tl, int tr, int pos) {
		if (tl > tr) return 0;
		if (tl == tr) return t[v];

		int tm = (tl+tr)/2;
		if (pos <= tm) return t[v]+get(v+1, tl, tm, pos);
		else return t[v]+get(v+2*(tm-tl+1), tm+1, tr, pos);
	}
};

signed main() {
	int n, m;
	cin >> n >> m;
	vi o(m);
	cin >> o;
	for (int i = 0; i < m; i++) o[i]--;

	vl p(n);
	cin >> p;
	int k;
	cin >> k;
	vector<Rain> lr(k);
	for (int i = 0; i < k; i++) {
		cin >> lr[i].l >> lr[i].r >> lr[i].a;
		lr[i].l--; lr[i].r--;
	}

	vvi c(n);
	for (int i = 0; i < m; i++) {
		c[o[i]].pb(i);
	}

	// map<pair<int, pii>, vi> b;
	vector<vector<pair<int, pii>>> b(k);
	for (int i = 0; i < n; i++) b[(k-1)/2].pb({i, {0, k-1}});

	vi res(n, -1);
	SegmentTree tree(m);
	while (LOG--) {
		tree.t = vl(2*m);
		int nxt = 0;
		vector<vector<pair<int, pii>>> tmp(k);
		for (int mid = 0; mid < k; mid++) {
			for (int i = nxt; i <= mid; i++) {
				if (lr[i].l <= lr[i].r) tree.update(1, 0, m-1, lr[i].l, lr[i].r, lr[i].a);
				else {
					tree.update(1, 0, m-1, lr[i].l, m-1, lr[i].a);
					tree.update(1, 0, m-1, 0, lr[i].r, lr[i].a);
				}
				nxt++;
			}
			for (auto key : b[mid]) {
				int l = key.second.first, r = key.second.second;
				int u = key.first;
				ll sum = 0;
				for (auto v : c[u]) {
					sum += tree.get(1, 0, m-1, v);
					if (sum >= p[u]) break;
				}
				// // cout << u << " " << l << " " <<r<< nL;
				if (sum < p[u]) {
					if (mid+1 <= r) tmp[(mid+1+r)/2].pb({u, {mid+1, r}});
				} else {
					if (l <= mid-1)
						tmp[(l+mid-1)/2].pb({u, {l, mid-1}});
					if (res[u] == -1) res[u] = mid+1;
					else res[u] = min(res[u], mid+1);
				}
			}
			b[mid].clear();
		}

		b = tmp;
		tmp.clear();
	}

	for (int i = 0; i < n; i++) {
		if (res[i] != -1) cout << res[i] << nL;
		else cout << "NIE" << nL;
	}

	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	348 ms	7172 KB	Output is correct
2	Correct	423 ms	11948 KB	Output is correct
3	Correct	405 ms	9708 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	399 ms	8288 KB	Output is correct
2	Correct	386 ms	8316 KB	Output is correct
3	Correct	394 ms	12096 KB	Output is correct
4	Correct	71 ms	6732 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	159 ms	7344 KB	Output is correct
2	Correct	259 ms	12764 KB	Output is correct
3	Correct	184 ms	5052 KB	Output is correct
4	Correct	389 ms	10728 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	376 ms	6068 KB	Output is correct
2	Correct	318 ms	9072 KB	Output is correct
3	Correct	369 ms	6292 KB	Output is correct
4	Correct	418 ms	12952 KB	Output is correct

Subtask #7
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3199 ms	61076 KB	Output is correct
2	Correct	1129 ms	33336 KB	Output is correct
3	Correct	895 ms	22044 KB	Output is correct
4	Runtime error	1041 ms	65536 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #8
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3205 ms	60944 KB	Output is correct
2	Correct	854 ms	33452 KB	Output is correct
3	Correct	725 ms	17588 KB	Output is correct
4	Runtime error	930 ms	65536 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

답안 #942528

Compilation message