oj.uz

Submission #881079

# Submission time Handle Problem Language Result Execution time Memory
881079 2023-11-30T14:23:20 Z phoenix0423 Meteors (POI11_met) C++17
100 / 100
 1161 ms 56808 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 4 ms 14456 KB Output is correct
3 Correct 5 ms 14240 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14412 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 18484 KB Output is correct
2 Correct 135 ms 24196 KB Output is correct
3 Correct 84 ms 18324 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 17896 KB Output is correct
2 Correct 101 ms 17864 KB Output is correct
3 Correct 127 ms 21960 KB Output is correct
4 Correct 21 ms 17940 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 17836 KB Output is correct
2 Correct 167 ms 22160 KB Output is correct
3 Correct 102 ms 16276 KB Output is correct
4 Correct 82 ms 18676 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 17276 KB Output is correct
2 Correct 121 ms 18112 KB Output is correct
3 Correct 64 ms 17360 KB Output is correct
4 Correct 112 ms 20152 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 976 ms 56808 KB Output is correct
2 Correct 682 ms 34552 KB Output is correct
3 Correct 541 ms 22884 KB Output is correct
4 Correct 1077 ms 47236 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 50168 KB Output is correct
2 Correct 720 ms 31528 KB Output is correct
3 Correct 433 ms 22716 KB Output is correct
4 Correct 1161 ms 54136 KB Output is correct