Submission #865176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
865176	2023-10-24T06:17:49 Z	vjudge1	Meteors (POI11_met)	C++17	24 / 100	61 ms	49328 KB

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 tl, tm
#define rs tm + 1, tr
#define pb push_back

using namespace std;

typedef long long ll;

const int N = 6e4 + 7;

int sz, root[N], n, m;

struct node {
	ll sum;
	int l, r;
	node() : sum(0), l(0), r(0) {}
} t[20 * N];

void build(int &v, int tl = 1, int tr = m) {
	if (!v) v = ++sz;
	if (tl == tr) return;
	build(t[v].l, ls);
	build(t[v].r, rs);
}

void upd(int pos, int val, int v1, int &v2, int tl = 1, int tr = m) {
	if (v1 != v2 || tl != 1 || tr != m) v2 = ++sz;
	if (tl == tr) {
		t[v2].sum = t[v1].sum + val;
		return;
	}
	if (pos <= tm) {
		t[v2].r = t[v1].r;
		upd(pos, val, t[v1].l, t[v2].l, ls);
	} else {
		t[v2].l = t[v1].l;
		upd(pos, val, t[v1].r, t[v2].r, rs);
	}
	int lv = t[v2].l, rv = t[v2].r;
	t[v2].sum = t[lv].sum + t[rv].sum;
}

ll res = 0;

void get(int r, int v, int tl = 1, int tr = m) {
	if (r < tl) return;
	if (tr <= r) {
		res += t[v].sum;
		return;
	}
	get(r, t[v].l, ls);
	get(r, t[v].r, rs);
}

int nd[N];
vector <int> pos[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int x;
	for (int i = 1; i <= m; i++) {
		cin >> x;
		pos[x].pb(i);
	}
	for (int i = 1; i <= n; i++) {
		cin >> nd[i];
	}
	int k;
	cin >> k;
	build(root[0]);
	int l, r;
	for (int i = 1; i <= k; i++) {
		cin >> l >> r >> x;
		if (l > r) {
			upd(1, x, root[i - 1], root[i]);
			upd(r + 1, -x, root[i], root[i]);
			upd(l, x, root[i], root[i]);
			continue;
		}
		upd(l, x, root[i - 1], root[i]);
		if (r < m) upd(r + 1, -x, root[i], root[i]);
	}
	int m;
	for (int i = 1; i <= n; i++) {
		l = 1; 
		r = k;
		while (l <= r) {
			m = l + r >> 1;
			res = 0;
			for (int it: pos[i]) {
				get(it, root[m]);
			}
			if (res >= nd[i]) r = m - 1;
			else l = m + 1;
		}
		if (l > k) cout << "NIE\n";
		else cout << l << '\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:16: note: in expansion of macro 'tm'
    7 | #define ls tl, tm
      |                ^~
met.cpp:28:16: note: in expansion of macro 'ls'
   28 |  build(t[v].l, ls);
      |                ^~
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:8:12: note: in expansion of macro 'tm'
    8 | #define rs tm + 1, tr
      |            ^~
met.cpp:29:16: note: in expansion of macro 'rs'
   29 |  build(t[v].r, rs);
      |                ^~
met.cpp: In function 'void upd(int, int, int, int&, int, int)':
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:38:13: note: in expansion of macro 'tm'
   38 |  if (pos <= tm) {
      |             ^~
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:7:16: note: in expansion of macro 'tm'
    7 | #define ls tl, tm
      |                ^~
met.cpp:40:35: note: in expansion of macro 'ls'
   40 |   upd(pos, val, t[v1].l, t[v2].l, ls);
      |                                   ^~
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:8:12: note: in expansion of macro 'tm'
    8 | #define rs tm + 1, tr
      |            ^~
met.cpp:43:35: note: in expansion of macro 'rs'
   43 |   upd(pos, val, t[v1].r, t[v2].r, rs);
      |                                   ^~
met.cpp: In function 'void get(int, int, int, int)':
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:7:16: note: in expansion of macro 'tm'
    7 | #define ls tl, tm
      |                ^~
met.cpp:57:17: note: in expansion of macro 'ls'
   57 |  get(r, t[v].l, ls);
      |                 ^~
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:8:12: note: in expansion of macro 'tm'
    8 | #define rs tm + 1, tr
      |            ^~
met.cpp:58:17: note: in expansion of macro 'rs'
   58 |  get(r, t[v].r, rs);
      |                 ^~
met.cpp: In function 'int main()':
met.cpp:97:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |    m = l + r >> 1;
      |        ~~^~~

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	20828 KB	Output is correct
2	Correct	5 ms	20676 KB	Output is correct
3	Correct	5 ms	20824 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	20824 KB	Output is correct
2	Correct	5 ms	20828 KB	Output is correct
3	Correct	5 ms	20668 KB	Output is correct

Subtask #3

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	39 ms	42836 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	39 ms	43344 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	37 ms	43176 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	39 ms	43092 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	59 ms	49328 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #8

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	61 ms	49096 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-