oj.uz

답안 #865161

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865161 2023-10-24T06:09:45 Z vjudge1 Meteors (POI11_met) C++17
24 / 100
 6000 ms 17240 KB 
#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

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

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 6488 KB Output is correct
2 Correct 84 ms 6612 KB Output is correct
3 Correct 126 ms 6612 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 6616 KB Output is correct
2 Correct 76 ms 6616 KB Output is correct
3 Correct 84 ms 6488 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6030 ms 7148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6040 ms 7472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6034 ms 7180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6017 ms 7000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6004 ms 17240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6004 ms 17164 KB Time limit exceeded
2 Halted 0 ms 0 KB -