oj.uz

Submission #652810

# Submission time Handle Problem Language Result Execution time Memory
652810 2022-10-24T15:22:14 Z flappybird Food Court (JOI21_foodcourt) C++17
13 / 100
 1000 ms 76584 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<ll, ll> 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<ll, ll> T;
struct segtree {
	vector<vector<T>> tree;
	vector<node> lazy;
	vector<ll> l, r;
	vector<ll> rcnt;
	ll s;
	ll qcnt = 0;
	void init(ll 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(ll N = 0) {
		s = 1 << (ll)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(ll low, ll high, ll t, ll num, ll 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(ll 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(ll low, ll high, ll num, ll 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(ll x, ll 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(ll x, ll t, ll loc = 1) {
		ll 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(ll l, ll r, ll t, ll n) {
		add(l, r, t, n);
		updnt(l, r, n);
		qcnt++;
	}
	void remove(ll l, ll r, ll n) { qcnt++; updnt(l, r, -n); }
	ll query(ll A, ll B) {
		qcnt++;
		ll nb = B + (gettcnt(A, qcnt) - getrcnt(A));
		ll l, r;
		if (gettcnt(A, qcnt) < nb) return -1;
		l = 0, r = qcnt;
		while (r - l > 1) {
			ll mid = (l + r + 1) / 2;
			if (gettcnt(A, mid) < nb) l = mid;
			else r = mid;
		}
		return r;
	}
};
ll cn[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N, Q;
	cin >> N >> Q >> Q;
	segtree seg(N);
	ll i;
	ll t, l, r, c, k, a;
	ll 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;
			ll 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 3 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 864 KB Output is correct
4 Correct 4 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 3 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 864 KB Output is correct
4 Correct 4 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 126 ms 14968 KB Output is correct
2 Correct 129 ms 15644 KB Output is correct
3 Correct 128 ms 15416 KB Output is correct
4 Correct 131 ms 15388 KB Output is correct
5 Correct 137 ms 16284 KB Output is correct
6 Correct 140 ms 16284 KB Output is correct
7 Incorrect 16 ms 1284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 76584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 22512 KB Output is correct
2 Correct 356 ms 23428 KB Output is correct
3 Correct 356 ms 23756 KB Output is correct
4 Correct 238 ms 20976 KB Output is correct
5 Correct 314 ms 22664 KB Output is correct
6 Correct 388 ms 24344 KB Output is correct
7 Correct 47 ms 1500 KB Output is correct
8 Correct 60 ms 1432 KB Output is correct
9 Correct 160 ms 19296 KB Output is correct
10 Correct 148 ms 21952 KB Output is correct
11 Correct 213 ms 24900 KB Output is correct
12 Correct 231 ms 24768 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 864 KB Output is correct
4 Correct 4 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 3 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 864 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -