oj.uz

답안 #931359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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