Submission #865161

#	Time	Username	Problem	Language	Result	Execution time	Memory
865161		vjudge1	Meteors (POI11_met)	C++17	24 / 100	6040 ms	17240 KiB

met

#include <bits/stdc++.h>
#define pb push_back
#define all(q) q.begin (), q.end ()
#define ll long long
#define f first
#define s second

using namespace std;

const ll MOD = 1e9 + 7;
const ll inf = 1e9 + 1;
const ll INF = 1e18 + 1;
const ll N = 2e6 + 1;
const int k = 15;

int u[N], o[N], p[N], t[N], ans[N];

void push (int v, int l, int r){
	if (l != r && u[v]){
		u[v + v] += u[v];
		u[v + v + 1] += u[v];
		int mid = (l + r) / 2;
		t[v + v] += (mid - l + 1) * u[v];
		t[v + v + 1] += (r - mid) * u[v];
		u[v] = 0;
	}
}

void upd (int v, int l, int r, int tl, int tr, int x){
	push (v, l, r);
	if (tl <= l && r <= tr){
		u[v] += x;
		t[v] += x * (r - l + 1);
		push(v, l, r);
		return;
	}
	if (l > tr || tl > r) return;
	ll mid = (l + r) / 2;
	upd (v + v, l, mid, tl, tr, x);
	upd (v + v + 1, mid + 1, r, tl, tr, x);
	t[v] = t[v + v] + t[v + v + 1];
}

ll get (int v, int l, int r, int tl, int tr){
	if (tl > r || l > tr) {/*cout << 3 << l << ' ' << r << '\n';*/ return 0ll;}
	if (tl <= l && r <= tr){
//		cout << 1 << l << ' ' << r << '\n';
		push (v, l, r);
		return t[v];
	}
	push (v, l, r);
	int mid = (l + r) / 2;
	return get (v + v, l, mid, tl, tr) + get (v + v + 1, mid + 1, r, tl, tr);
}

void solve (){
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i){
		cin >> o[i];
	}
	for (int i = 1; i <= n; ++i){
		cin >> p[i];
	}
	int k, ti = 0;
	cin >> k;
	while (k--){
		++ti;
		int l, r, x;
		cin >> l >> r >> x;
		if (l <= r){
			upd (1, 1, m, l, r, x);
//			for (int i = 1; i <= 9; ++i) cout << t[i] << ' ';
//			cout << '\n';
		}
		else {
			upd (1, 1, m, l, m, x);
			upd (1, 1, m, 1, r, x);
//			for (int i = 1; i <= 9; ++i) cout << t[i] << ' ';
//			cout << '\n';
		}
		vector <ll> a (n + 1, 0);
		for (int i = 1; i <= m; ++i){
			ll q = get (1, 1, m, i, i);
			a[o[i]] += q;
		}
		for (int i = 1; i <= n; ++i){
			if (a[i] >= p[i] && !ans[i]) ans[i] = ti;
		}
	}
	for (int i = 1; i <= n; ++i){
		if (ans[i]) cout << ans[i] << '\n';
		else cout << "NIE\n";
	}
}

main (){
	ios_base::sync_with_stdio (0);
	cin.tie (0);
//	freopen("guard.in", "r", stdin);
//	freopen("guard.out", "w", stdout);
	ll t = 1;
//	cin >> t;
	for (ll i = 1; i <= t; ++i){
//		cout << "Case " << i << ':' << '\n';
		solve ();
//		cout << '\n';
	}
}

Compilation message (stderr)

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

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13