Submission #931359

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
931359	2024-02-21T16:13:36 Z	aliarapov	Meteors (POI11_met)	C++17	100 / 100	2434 ms	65536 KB

#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

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

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	19804 KB	Output is correct
2	Correct	10 ms	19800 KB	Output is correct
3	Correct	7 ms	19804 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	19804 KB	Output is correct
2	Correct	5 ms	19800 KB	Output is correct
3	Correct	7 ms	19804 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	24916 KB	Output is correct
2	Correct	174 ms	30728 KB	Output is correct
3	Correct	255 ms	24660 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	211 ms	24224 KB	Output is correct
2	Correct	253 ms	24404 KB	Output is correct
3	Correct	127 ms	27852 KB	Output is correct
4	Correct	56 ms	25424 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	115 ms	23992 KB	Output is correct
2	Correct	183 ms	28584 KB	Output is correct
3	Correct	38 ms	20452 KB	Output is correct
4	Correct	221 ms	25040 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	23580 KB	Output is correct
2	Correct	185 ms	24444 KB	Output is correct
3	Correct	139 ms	23740 KB	Output is correct
4	Correct	225 ms	26640 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1297 ms	65536 KB	Output is correct
2	Correct	202 ms	46492 KB	Output is correct
3	Correct	232 ms	22352 KB	Output is correct
4	Correct	2434 ms	60860 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1196 ms	63416 KB	Output is correct
2	Correct	290 ms	44216 KB	Output is correct
3	Correct	78 ms	23268 KB	Output is correct
4	Correct	2360 ms	65536 KB	Output is correct