oj.uz

Submission #880786

# Submission time Handle Problem Language Result Execution time Memory
880786 2023-11-30T04:02:12 Z phoenix0423 Meteors (POI11_met) C++17
74 / 100
 869 ms 56460 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 + 1 == r){
		for(auto x : a) ans[x] = r;
		return;
	}
	int m = (l + r) / 2;
	for(int i = l + 1; 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(tar[id] - cnt <= 0) to_l.pb(id);
		else tar[id] -= cnt, to_r.pb(id);
	}
	for(int i = l + 1; i <= m; i++){
		auto [l, r, val] = op[i];
		update(l, r, -val);
	}
	solve(to_l, l, m);
	solve(to_r, m, 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, -1, 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 14424 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 4 ms 14428 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 18396 KB Output is correct
2 Correct 135 ms 25028 KB Output is correct
3 Correct 84 ms 18340 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 17868 KB Output is correct
2 Correct 102 ms 17936 KB Output is correct
3 Correct 134 ms 21904 KB Output is correct
4 Correct 27 ms 18104 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 17776 KB Output is correct
2 Correct 170 ms 22648 KB Output is correct
3 Correct 97 ms 16276 KB Output is correct
4 Correct 90 ms 18664 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 17340 KB Output is correct
2 Correct 116 ms 18112 KB Output is correct
3 Correct 65 ms 17356 KB Output is correct
4 Correct 115 ms 20384 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 56460 KB Output is correct
2 Incorrect 634 ms 33860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 50388 KB Output is correct
2 Incorrect 705 ms 32128 KB Output isn't correct
3 Halted 0 ms 0 KB -