oj.uz

답안 #865337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865337 2023-10-24T07:32:57 Z vjudge1 Meteors (POI11_met) C++17
100 / 100
 3283 ms 65536 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

#define tm (tl + tr >> 1)
#define ls v << 1, tl, tm
#define rs v << 1 | 1, tm + 1, tr
#define pb push_back

using namespace std;

typedef long long ll;

const int N = 3e5 + 7;

int n, m;
ll t[N << 2];

void build(int v = 1, int tl = 1, int tr = m) {
	t[v] = 0;
	if (tl == tr) return;
	build(ls);
	build(rs);
}

void upd(int pos, int val, int v = 1, int tl = 1, int tr = m) {
	if (tl == tr) {
		t[v] += val;
		return;
	}
	if (pos <= tm) upd(pos, val, ls);
	else upd(pos, val, rs);
	t[v] = t[v << 1] + t[v << 1 | 1];
}

ll get(int r, int v = 1, int tl = 1, int tr = m) {
	if (r < tl) return 0;
	if (tr <= r) return t[v];
	return get(r, ls) + get(r, rs);
}

int nd[N], ansl[N], ansr[N], ql[N], qr[N], qx[N];
vector <int> pos[N], act[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		pos[x].pb(i);
	}
	for (int i = 1; i <= n; i++) {
		cin >> nd[i];
	}
	int k;
	cin >> k;
	for (int i = 1; i <= k; i++) {
		cin >> ql[i] >> qr[i] >> qx[i];		
	}
	for (int i = 1; i <= n; i++) {
		ansl[i] = 1;
		ansr[i] = k;
	}
	while (1) {
		bool ok = 0;
		build();
		for (int i = 1; i <= n; i++) {
			if (ansl[i] <= ansr[i]) {
				ok = 1;
				ll m = ansl[i] + ansr[i] >> 1;
				act[m].pb(i);
			}
		}
		if (!ok) break;
		for (int i = 1; i <= k; i++) {
			if (ql[i] > qr[i]) {
				upd(1, qx[i]);
				upd(qr[i] + 1, -qx[i]);
				upd(ql[i], qx[i]);
			} else {
				upd(ql[i], qx[i]);
				if (qr[i] < m) upd(qr[i] + 1, -qx[i]);
			}
			for (int it: act[i]) {
				ll ans = 0;
				for (int cur: pos[it]) {
					ans += get(cur);
					if (ans >= nd[it]) break;
				}
//				cout << i << ' ' << it << ' ' << ans << ' ' << ansl[it] << ' ' << ansr[it] << '\n';
				if (ans >= nd[it]) ansr[it] = i - 1;
				else ansl[it] = i + 1;
			}
		}
		for (int i = 0; i <= k + 1; i++) {
			act[i].clear();
		}
	}
	for (int i = 1; i <= n; i++) {
		if (ansl[i] > k) cout << "NIE\n";
		else cout << ansl[i] << '\n';
	}
}

Compilation message

met.cpp: In function 'void build(int, int, int)':
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:7:24: note: in expansion of macro 'tm'
    7 | #define ls v << 1, tl, tm
      |                        ^~
met.cpp:23:8: note: in expansion of macro 'ls'
   23 |  build(ls);
      |        ^~
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:8:24: note: in expansion of macro 'tm'
    8 | #define rs v << 1 | 1, tm + 1, tr
      |                        ^~
met.cpp:24:8: note: in expansion of macro 'rs'
   24 |  build(rs);
      |        ^~
met.cpp: In function 'void upd(int, int, int, int, int)':
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:32:13: note: in expansion of macro 'tm'
   32 |  if (pos <= tm) upd(pos, val, ls);
      |             ^~
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:7:24: note: in expansion of macro 'tm'
    7 | #define ls v << 1, tl, tm
      |                        ^~
met.cpp:32:31: note: in expansion of macro 'ls'
   32 |  if (pos <= tm) upd(pos, val, ls);
      |                               ^~
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:8:24: note: in expansion of macro 'tm'
    8 | #define rs v << 1 | 1, tm + 1, tr
      |                        ^~
met.cpp:33:21: note: in expansion of macro 'rs'
   33 |  else upd(pos, val, rs);
      |                     ^~
met.cpp: In function 'll get(int, int, int, int)':
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:7:24: note: in expansion of macro 'tm'
    7 | #define ls v << 1, tl, tm
      |                        ^~
met.cpp:40:16: note: in expansion of macro 'ls'
   40 |  return get(r, ls) + get(r, rs);
      |                ^~
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:8:24: note: in expansion of macro 'tm'
    8 | #define rs v << 1 | 1, tm + 1, tr
      |                        ^~
met.cpp:40:29: note: in expansion of macro 'rs'
   40 |  return get(r, ls) + get(r, rs);
      |                             ^~
met.cpp: In function 'int main()':
met.cpp:74:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     ll m = ansl[i] + ansr[i] >> 1;
      |            ~~~~~~~~^~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 23132 KB Output is correct
2 Correct 6 ms 23132 KB Output is correct
3 Correct 8 ms 23388 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 6 ms 23132 KB Output is correct
3 Correct 7 ms 23132 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 23860 KB Output is correct
2 Correct 311 ms 25684 KB Output is correct
3 Correct 268 ms 25284 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 24912 KB Output is correct
2 Correct 284 ms 24888 KB Output is correct
3 Correct 282 ms 25684 KB Output is correct
4 Correct 61 ms 24932 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 24348 KB Output is correct
2 Correct 230 ms 26256 KB Output is correct
3 Correct 122 ms 23132 KB Output is correct
4 Correct 262 ms 25576 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 23516 KB Output is correct
2 Correct 249 ms 24912 KB Output is correct
3 Correct 231 ms 23692 KB Output is correct
4 Correct 292 ms 26964 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2581 ms 42352 KB Output is correct
2 Correct 1783 ms 31120 KB Output is correct
3 Correct 650 ms 25548 KB Output is correct
4 Correct 3248 ms 65536 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2546 ms 41268 KB Output is correct
2 Correct 1106 ms 31112 KB Output is correct
3 Correct 532 ms 26708 KB Output is correct
4 Correct 3283 ms 65536 KB Output is correct