oj.uz

Submission #865335

# Submission time Handle Problem Language Result Execution time Memory
865335 2023-10-24T07:31:55 Z vjudge1 Meteors (POI11_met) C++17
74 / 100
 2495 ms 38044 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, 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:22:8: note: in expansion of macro 'ls'
   22 |  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:23:8: note: in expansion of macro 'rs'
   23 |  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:31:13: note: in expansion of macro 'tm'
   31 |  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:31:31: note: in expansion of macro 'ls'
   31 |  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:32:21: note: in expansion of macro 'rs'
   32 |  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:39:16: note: in expansion of macro 'ls'
   39 |  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:39:29: note: in expansion of macro 'rs'
   39 |  return get(r, ls) + get(r, rs);
      |                             ^~
met.cpp: In function 'int main()':
met.cpp:73:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     ll m = ansl[i] + ansr[i] >> 1;
      |            ~~~~~~~~^~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23132 KB Output is correct
2 Correct 7 ms 23132 KB Output is correct
3 Correct 7 ms 23132 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 7 ms 23132 KB Output is correct
3 Correct 8 ms 23132 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 23912 KB Output is correct
2 Correct 298 ms 25680 KB Output is correct
3 Correct 275 ms 25424 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 24776 KB Output is correct
2 Correct 266 ms 24916 KB Output is correct
3 Correct 274 ms 25684 KB Output is correct
4 Correct 62 ms 24660 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 24400 KB Output is correct
2 Correct 226 ms 26132 KB Output is correct
3 Correct 120 ms 23132 KB Output is correct
4 Correct 262 ms 25736 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 23536 KB Output is correct
2 Correct 239 ms 24928 KB Output is correct
3 Correct 235 ms 23744 KB Output is correct
4 Correct 290 ms 26804 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2485 ms 38044 KB Output is correct
2 Incorrect 1493 ms 27012 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2495 ms 36864 KB Output is correct
2 Incorrect 1153 ms 26996 KB Output isn't correct
3 Halted 0 ms 0 KB -