Submission #881079

#	Time	Username	Problem	Language	Result	Execution time	Memory
881079		phoenix0423	Meteors (POI11_met)	C++17	100 / 100	1161 ms	56808 KiB

met

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 0, n + 1)
#define pb push_back
#define pf push_front
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
#define int long long 
const int INF = 1e9 + 7;
const int maxn = 3e5 + 5;

struct info{
	ll l, r, val;
	info(){}
	info(ll _l, ll _r, ll _val) : l(_l), r(_r), val(_val){}
};
int n, m;
vector<info> op;
vector<int> pos[maxn];
ll tar[maxn], ans[maxn];
ll BIT[maxn];

void upd(int pos, ll val){
	pos++;
	while(pos < maxn){
		BIT[pos] += val;
		pos += lowbit(pos);
	}
}
ll qry(int pos){
	pos++;
	ll ret = 0;
	while(pos > 0){
		ret += BIT[pos];
		pos -= lowbit(pos);
	}
	return ret;
}
void update(int l, int r, int val){
	if(l <= r){
		upd(l, val);
		upd(r + 1, -val);
	}
	else{
		swap(l, r);
		upd(0, val);
		upd(l + 1, -val);
		upd(r, val);
	}
}
void solve(vector<int> a, int l, int r){
	if(l == r){
		for(auto x : a) ans[x] = r;
		return;
	}
	int m = (l + r) / 2;
	for(int i = l; i <= m; i++){
		auto [l, r, val] = op[i];
		update(l, r, val);
	}
	vector<int> to_l, to_r;
	for(auto id : a){
		ll cnt = 0;
		for(auto p : pos[id]){
			cnt += qry(p);
			if(cnt >= tar[id]) break;
		}
		if(tar[id] - cnt <= 0) to_l.pb(id);
		else tar[id] -= cnt, to_r.pb(id);
	}
	for(int i = l; i <= m; i++){
		auto [l, r, val] = op[i];
		update(l, r, -val);
	}
	solve(to_l, l, m);
	solve(to_r, m + 1, r);

}
signed main(void){
	fastio;
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		int x;
		cin>>x;
		x--;
		pos[x].pb(i);
	}
	for(int i = 0; i < n; i++){
		cin>>tar[i];
	}
	int k;
	cin>>k;
	for(int i = 0; i < k; i++){
		int l, r, v;
		cin>>l>>r>>v;
		l--, r--;
		op.pb(info(l, r, v));
	}
	vector<int> a(n);
	for(int i = 0; i < n; i++) a[i] = i;
	solve(a, 0, k);
	for(int i = 0; i < n; i++){
		if(ans[i] == k) cout<<"NIE\n";
		else cout<<ans[i] + 1<<"\n";
	}
}

• 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