답안 #865169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
865169	2023-10-24T06:13:41 Z	vjudge1	Meteors (POI11_met)	C++17	0 / 100	54 ms	35620 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 = 4e4 + 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;
}

void upd2(int pos, int val, int &v, int tl = 1, int tr = m) {
	if (!v) v = ++sz;
	if (tl == tr) {
		t[v].sum += val;
		return;
	}
	if (pos <= tm) {
		upd2(pos, val, t[v].l, ls);
	} else {
		upd2(pos, val, t[v].r, rs);
	}
	t[v].sum = t[t[v].l].sum + t[t[v].r].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]);
			upd2(r + 1, -x, root[i]);
			upd2(l, x, root[i]);
			continue;
		}
		upd(l, x, root[i - 1], root[i]);
		if (r < m) upd2(r + 1, -x, 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 upd2(int, int, int&, int, int)':
met.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    6 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
met.cpp:55:13: note: in expansion of macro 'tm'
   55 |  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:56:26: note: in expansion of macro 'ls'
   56 |   upd2(pos, val, 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:26: note: in expansion of macro 'rs'
   58 |   upd2(pos, val, t[v].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:71:17: note: in expansion of macro 'ls'
   71 |  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:72:17: note: in expansion of macro 'rs'
   72 |  get(r, t[v].r, rs);
      |                 ^~
met.cpp: In function 'int main()':
met.cpp:111:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |    m = l + r >> 1;
      |        ~~^~~

Subtask #1

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	13912 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	13916 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	34 ms	29008 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	38 ms	29248 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	30 ms	29212 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	39 ms	29008 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	54 ms	35620 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #8

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	51 ms	35152 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-