oj.uz

Submission #652795

# Submission time Handle Problem Language Result Execution time Memory
652795 2022-10-24T14:32:51 Z flappybird Food Court (JOI21_foodcourt) C++17
0 / 100
 182 ms 45956 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 251010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
struct node {
	ll a, b;
	node(ll a = 0, ll b = 0) :a(a), b(b) {}
};
node operator+(node& n1, node& n2) {
	node ret;
	ret.a = min(n1.a, n1.b + n2.a);
	ret.b = n1.b + n2.b;
	return ret;
}
void operator+= (node& n1, node& n2) { n1 = n1 + n2; }
void operator+=(node& n1, ll x) {
	n1.b += x;
	n1.a = min(n1.a, n1.b);
}
void operator+=(ll& x, node n1) {
	x += n1.a;
	ll ub = n1.b - n1.a;
	x = max(x, 0ll);
	x += ub;
}
typedef pair<int, ll> T;
struct segtree {
	vector<vector<T>> tree;
	vector<node> lazy;
	vector<int> l, r;
	vector<ll> rcnt;
	int s;
	int qcnt = 0;
	void init(int x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s + 1;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
	}
	segtree(int N = 0) {
		s = 1 << (int)ceil(log2(N));
		tree = vector<vector<T>>(2 * s + 1, vector<T>(1, T(0, 0ll)));
		lazy.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
		rcnt.resize(2 * s + 1);
		init();
	}
	void add(int low, int high, int t, int num, int loc = 1) {
		if (low == l[loc] && high == r[loc]) {
			tree[loc].emplace_back(t, num + tree[loc].back().second);
			return;
		}
		if (high <= r[loc * 2]) add(low, high, t, num, loc * 2);
		else if (low >= l[loc * 2 + 1]) add(low, high, t, num, loc * 2 + 1);
		else add(low, r[loc * 2], t, num, loc * 2), add(l[loc * 2 + 1], high, t, num, loc * 2 + 1);
	}
	void prop(int loc) {
		if (loc >= s) return;
		for (auto c : { loc * 2, loc * 2 + 1 }) {
			rcnt[c] += lazy[loc];
			lazy[c] += lazy[loc];
		}
		lazy[loc] = node();
	}
	void updnt(int low, int high, int num, int loc = 1) {
		prop(loc);
		if (low == l[loc] && high == r[loc]) {
			rcnt[loc] += num;
			lazy[loc] += num;
			return;
		}
		if (high <= r[loc * 2]) updnt(low, high, num, loc * 2);
		else if (low >= l[loc * 2 + 1]) updnt(low, high, num, loc * 2 + 1);
		else updnt(low, r[loc * 2], num, loc * 2), updnt(l[loc * 2 + 1], high, num, loc * 2 + 1);
		rcnt[loc] = min(rcnt[loc * 2], rcnt[loc * 2 + 1]);
	}
	ll getrcnt(int x, int loc = 1) {
		prop(loc);
		if (l[loc] == r[loc]) return rcnt[loc];
		if (x <= r[loc * 2]) return getrcnt(x, loc * 2);
		else return getrcnt(x, loc * 2 + 1);
	}
	ll gettcnt(int x, int t, int loc = 1) {
		int ind = upper_bound(tree[loc].begin(), tree[loc].end(), T(t + 1, -1)) - tree[loc].begin();
		ind--;
		ll ans;
		if (ind < 0) ans = 0;
		else ans = tree[loc][ind].second;
		if (l[loc] == r[loc]) return ans;
		if (x <= r[loc * 2]) return ans + gettcnt(x, t, loc * 2);
		else return ans + gettcnt(x, t, loc * 2 + 1);
	}
	void update(int l, int r, int t, int n) {
		add(l, r, t, n);
		updnt(l, r, n);
		qcnt++;
	}
	void remove(int l, int r, int n) { qcnt++; updnt(l, r, -n); }
	int query(int A, ll B) {
		qcnt++;
		ll nb = B + (gettcnt(A, qcnt) - getrcnt(A));
		int l, r;
		if (gettcnt(A, qcnt) < nb) return -1;
		l = 0, r = qcnt;
		while (r - l > 1) {
			int mid = (l + r + 1) / 2;
			if (gettcnt(A, mid) < nb) l = mid;
			else r = mid;
		}
		return r;
	}
};
int cn[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, Q;
	cin >> N >> Q >> Q;
	segtree seg(N);
	int i;
	int t, l, r, c, k, a, b;
	for (i = 1; i <= Q; i++) {
		cin >> t;
		if (t == 1) cin >> l >> r >> c >> k, seg.update(l, r, i, k), cn[i] = c;
		if (t == 2) cin >> l >> r >> k, seg.remove(l, r, k);
		if (t == 3) {
			cin >> a >> b;
			int res = seg.query(a, b);
			if (!~res) cout << 0 << ln;
			else cout << cn[res] << ln;
		}
	}
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 14892 KB Output is correct
2 Correct 154 ms 15640 KB Output is correct
3 Correct 141 ms 15348 KB Output is correct
4 Correct 130 ms 15356 KB Output is correct
5 Correct 153 ms 16340 KB Output is correct
6 Correct 137 ms 16236 KB Output is correct
7 Incorrect 20 ms 1872 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -