oj.uz

Submission #865331

# Submission time Handle Problem Language Result Execution time Memory
865331 2023-10-24T07:30:09 Z vjudge1 Meteors (POI11_met) C++17
74 / 100
 2510 ms 38356 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;
				int 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);
				}
//				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:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int 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 6 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 7 ms 23128 KB Output is correct
2 Correct 7 ms 23220 KB Output is correct
3 Correct 7 ms 23260 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 23932 KB Output is correct
2 Correct 300 ms 25676 KB Output is correct
3 Correct 264 ms 25448 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 24912 KB Output is correct
2 Correct 264 ms 24772 KB Output is correct
3 Correct 306 ms 25760 KB Output is correct
4 Correct 62 ms 24712 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 24400 KB Output is correct
2 Correct 226 ms 26332 KB Output is correct
3 Correct 122 ms 23128 KB Output is correct
4 Correct 251 ms 25684 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 23532 KB Output is correct
2 Correct 262 ms 24896 KB Output is correct
3 Correct 223 ms 23636 KB Output is correct
4 Correct 281 ms 26960 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2510 ms 38356 KB Output is correct
2 Incorrect 1628 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 2500 ms 36956 KB Output is correct
2 Incorrect 1272 ms 26996 KB Output isn't correct
3 Halted 0 ms 0 KB -