Submission #1246455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246455		cheng0928	Meteors (POI11_met)	C++20	74 / 100	440 ms	22108 KiB

met

#include <bits/stdc++.h>
#define int long long //TLE or MLE remove
#define F first
#define S second
#define Cheng0928 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SIZE(a) signed(a.size())
#define rALL(x) x.rbegin(), x.rend()
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define MP make_pair
 
using namespace std;

const int MN = 3e5 + 2;
const int INF = 9e18;
const int MOD = 998244353;

int bit[MN];

void ins(int i, int x){
	for(i; i < MN; i += (i & -i)) bit[i] += x;
}

int qu(int i){
	int ret = 0;
	for(i; i > 0; i -= (i & -i)) ret += bit[i];
	return ret;
}

struct Q{
	int l, r;
	vector<int> ids;
};

void sol(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> con(n + 1);
	for(int i = 1; i <= m; i++){
		int x;
		cin >> x;
		con[x].PB(i);
	}
	vector<int> need(n + 1);
	for(int i = 1; i <= n; i++) cin >> need[i];
	int q;
	cin >> q;
	vector<array<int,3>> oper(q + 1);
	for(int i = 1; i <= q; i++){
		for(int j = 0; j < 3; j++) cin >> oper[i][j];
	}
	queue<Q> bns;
	{
		vector<int> tmp;
		for(int i = 1; i <= n; i++) tmp.PB(i);
		bns.push({1, q + 1, tmp});
	}
	int ptr = 0;
	vector<int> ans(n + 1);
	while(!bns.empty()){
		auto [l, r, ids] = bns.front();
		bns.pop();
		if(l == r){
			for(int id : ids){
				int sum = 0;
				for(int x : con[id]){
					sum += qu(x);
				}
				ans[id] = l;
			}
			continue;
		}
		int mid = (l + r) >> 1;
		if(mid < ptr){
			for(int i = 1; i < MN; i++) bit[i] = 0;
			ptr = 0;
		}
		while(ptr < mid){
			auto [l, r, a] = oper[++ptr];
			ins(l, a), ins(r + 1, -a);
			if(r < l) ins(1, a);
		}
		vector<int> sm, bi;
		for(int id : ids){
			int sum = 0;
			for(int x : con[id]){
				sum += qu(x);
			}
			if(need[id] <= sum) sm.PB(id);
			else bi.PB(id);
		}
		if(!sm.empty()) bns.push({l, mid, sm});
		if(!bi.empty()) bns.push({mid + 1, r, bi});
	}
	for(int i = 1; i <= n; i++){
		cout << (ans[i] == q + 1 ? "NIE" : to_string(ans[i])) << '\n';
	}
}
signed main()
{
    Cheng0928
    int t;
    t = 1;
    //cin >> t;
    while(t--) sol();
    return 0;
}

• 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: 0 / 13
• Subtask 8: 0 / 13