oj.uz

Submission #865165

# Submission time Handle Problem Language Result Execution time Memory
865165 2023-10-24T06:12:39 Z vjudge1 Meteors (POI11_met) C++17
0 / 100
 53 ms 35668 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 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 (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:54:13: note: in expansion of macro 'tm'
   54 |  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:55:26: note: in expansion of macro 'ls'
   55 |   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:57:26: note: in expansion of macro 'rs'
   57 |   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:70:17: note: in expansion of macro 'ls'
   70 |  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:71:17: note: in expansion of macro 'rs'
   71 |  get(r, t[v].r, rs);
      |                 ^~
met.cpp: In function 'int main()':
met.cpp:110:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |    m = l + r >> 1;
      |        ~~^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 13916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 28936 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 38 ms 29272 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 31 ms 29264 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 29008 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 52 ms 35668 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 53 ms 35136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -