Submission #1145871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145871		Kel_Mahmut	새로운 문제 (POI11_met)	C++20	100 / 100	2354 ms	53188 KiB

met

#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct fenwick{
	int n;
	vector<ll> fen;
	fenwick(int n) : n(n), fen(n) {}

	void add(int i, ll val){
		for(; i < n; i |= i + 1)
			fen[i] += val;
	}

	void reset(){
		for(int i = 0; i < n; i++)
			fen[i] = 0;
	}

	ll query(int i){
		ll ret = 0;
		for(; i >= 0; i = (i & (i + 1)) - 1)
			ret += fen[i];
		return ret;
	}

	ll query(int l, int r){
		return query(r) - query(l - 1);
	}
};

int main(){
	// ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, m;
	cin >> n >> m; // m tane eleman var,    n tane marka var
	vector<ll> a(m);
	vector<ll> p(n);
	for(int i = 0; i < m; i++) cin >> a[i], a[i]--;
	for(int i = 0; i < n; i++) cin >> p[i];
	int q;
	cin >> q;
	vector<array<ll, 3>> s;
	s.pb({0, 0, 0});
	for(int i = 0; i < q; i++){
		ll l, r, x;
		cin >> l >> r >> x;
		l--, r--;
		s.pb({l, r, x});
	}

	fenwick fen(m);
	auto Apply = [&](int i){
		auto [l, r, x] = s[i];
		if(l <= r){
			fen.add(l, x);
			fen.add(r + 1, -x);
		}
		else{
			fen.add(0, x);
			fen.add(r + 1, -x);
			fen.add(l, x);
		}
	};

	queue<array<ll, 4>> search; // tm, marka, tl, tr
	vector<array<ll, 4>> new_search; // aynisi ama yeni queryler icin
	ll tl = 0, tr = q + 1;
	for(int i = 0; i < n; i++){
		search.push({(tl + tr) / 2, i, tl, tr});
	}

	vector<vector<int>> gec(n);
	for(int i = 0; i < m; i++){
		gec[a[i]].pb(i);
	}

	vector<ll> ans(n);
	for(int rep = 0; rep < 40; rep++){

		for(int i = 0; i <= q; i++){
			Apply(i);
			while(!search.empty() && search.front()[0] == i){
				ll cev = 0;
				auto [tm, marka, tl, tr] = search.front();
				search.pop();

				for(int ind : gec[marka]){
					cev += fen.query(ind);
					if(cev >= p[marka]) break;
				}

				if(cev >= p[marka]){
					ll new_tr = tm;
					ll new_tm = (tl + new_tr) / 2;
					new_search.pb({new_tm, marka, tl, new_tr});
				}
				else{
					ll new_tl = tm;
					ll new_tm = (new_tl + tr) / 2;
					new_search.pb({new_tm, marka, new_tl, tr});
				}
			}
		}
		assert(search.empty());
		sort(all(new_search));
		for(auto ar : new_search){
			search.push(ar);
			ans[ar[1]] = ar[3];
		}
		new_search.clear();
		fen.reset();
	}

	for(int i = 0; i < n; i++){
		if(ans[i] == q + 1)
			cout << "NIE" << endl;
		else
			cout << ans[i] << endl;
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13