oj.uz

Submission #652806

# Submission time Handle Problem Language Result Execution time Memory
652806 2022-10-24T15:19:47 Z flappybird Food Court (JOI21_foodcourt) C++17
13 / 100
 1000 ms 77152 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;
	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;
			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 3 ms 724 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Incorrect 2 ms 336 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 724 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 13724 KB Output is correct
2 Correct 118 ms 14316 KB Output is correct
3 Correct 122 ms 14164 KB Output is correct
4 Correct 118 ms 14092 KB Output is correct
5 Correct 123 ms 15144 KB Output is correct
6 Correct 119 ms 15068 KB Output is correct
7 Incorrect 20 ms 1112 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 1089 ms 77152 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 724 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Incorrect 2 ms 336 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 339 ms 22664 KB Output is correct
2 Correct 357 ms 23792 KB Output is correct
3 Correct 359 ms 24268 KB Output is correct
4 Correct 237 ms 21016 KB Output is correct
5 Correct 308 ms 22848 KB Output is correct
6 Correct 346 ms 24632 KB Output is correct
7 Correct 46 ms 2420 KB Output is correct
8 Correct 59 ms 2244 KB Output is correct
9 Correct 163 ms 19604 KB Output is correct
10 Correct 145 ms 21864 KB Output is correct
11 Correct 214 ms 25180 KB Output is correct
12 Correct 225 ms 25156 KB Output is correct

Subtask #7
0 / 26.0

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