Submission #931359

#	Time	Username	Problem	Language	Result	Execution time	Memory
931359		aliarapov	Meteors (POI11_met)	C++17	100 / 100	2434 ms	65536 KiB

met

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int)v.size()
 
const int INF = 1e18;
const int mod = 1e9 + 7;
const int N = 3e5+5;
int need[N], ans[N], n, m;
vector<tuple<int,int,int> > q(N);
vector<int> own[N];
int t[4 * N], lazy[4 * N];

void push(int v, int tl, int tr){
	 if(tl ^ tr){
		 lazy[v << 1] += lazy[v];
		 lazy[v << 1 | 1] += lazy[v];
	 }
	 t[v] += (tr - tl + 1) * lazy[v];
	 lazy[v] = 0;
}

void update(int l, int r, int val, int v = 1, int tl = 1, int tr = m){
	if(tl > r or tr < l) return;
	if(l <= tl and tr <= r){
		lazy[v] += val;
		push(v, tl, tr);
	}else{
		push(v, tl, tr);
		int tm = (tl + tr) >> 1;
		update(l, r, val, v << 1, tl, tm);
		update(l, r, val, v << 1 | 1, tm + 1, tr);
		t[v] = t[v << 1] + t[v << 1 | 1];
	}
}

int get(int pos, int v = 1, int tl = 1, int tr = m){
	push(v, tl, tr);
	if(tl == tr){
		return t[v];
	}else{
		int tm = (tl + tr) >> 1;
		if(pos <= tm) return get(pos, v << 1, tl, tm);
		else return get(pos, v << 1 | 1, tm + 1, tr);
	}
}

void rec(int l, int r, vector<int> a, int &at){
	if(a.empty()) return;
	int tm = (l + r) >> 1;
	while(at < tm){
		auto [tl, tr, val] = q[++at];
		if(tl <= tr) update(tl, tr, val);
		else update(1, tr, val), update(tl, m, val);
	}
	while(at > tm){
		auto [tl, tr, val] = q[at--];
		if(tl <= tr) update(tl, tr, -val);
		else update(1, tr, -val), update(tl, m, -val);
	}
	
	vector<int> la, ra;
	for(int i : a){
		int res = 0;
		for(int j : own[i]){
			res += get(j);
			if(res >= need[i]) break;
		}
		
		if(res < need[i]){
			ra.pb(i);
		}else{
			la.pb(i);
			ans[i] = r;
		}
	}
	
	a.clear();
	if(l < r){
		rec(l, tm, la, at);
		rec(tm + 1, r, ra, at);
	}
}

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int at; cin >> at;
		own[at].pb(i);
	}
	for(int i = 1; i <= n; i++) cin >> need[i];
	int k; cin >> k;
	for(int i = 1; i <= k; i++){
		int l, r, a;
		cin >> l >> r >> a;
		q[i] = {l, r, a};
	}
	vector<int> a(n);
	iota(all(a), 1);
	int at = 0;
	rec(1, k, a, at);
	
	for(int i = 1; i <= n; i++){
		if(ans[i] == 0) cout << "NIE\n";
		else cout << ans[i] << '\n';
	}
}

main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
	}
}

Compilation message (stderr)

met.cpp:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  115 | main(){
      | ^~~~

• 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