Submission #865335

#	Time	Username	Problem	Language	Result	Execution time	Memory
865335		vjudge1	Meteors (POI11_met)	C++17	74 / 100	2495 ms	38044 KiB

met

//#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 (stderr)

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13