Submission #425990

# Submission time Handle Problem Language Result Execution time Memory
425990 2021-06-13T12:48:11 Z Kevin_Zhang_TW Food Court (JOI21_foodcourt) C++17
13 / 100
576 ms 41088 KB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;
const ll inf = 1ll << 60;

int n, m, q;
int res[MAX_N], cid[MAX_N];

bool is_leave[MAX_N];

//          position, delta
vector<pair<int,ll>> rec[MAX_N];
//         time, k
vector<pair<int,ll>> allq[MAX_N];

struct sgt {
	struct node {
		ll mn, pos, tg;
		void operator += (ll v) {
			mn += v, tg += v;
		}
		node (node a, node b) {
			mn = min(a.mn, b.mn);
			if (a.mn == mn) pos = a.pos;
			else pos = b.pos;
			tg = 0;
		}
		node () : mn(0), pos(0), tg(0) {}
		pair<ll,ll> get() { return make_pair(mn, pos); }
	};
	int n;
	vector<node> val;
	sgt(int n) : n(n) {
		val.resize(n<<1);
		for (int i = 0;i < n;++i)
			val[i+n].pos = i;
	}
	void add(int l, int r, ll v) {
		int sl = l+=n, sr = r+=n;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++] += v;
			if (r&1) val[--r] += v;
		}
		for (;sl>>=1, sr>>=1;) 
			upd(sl), upd(sr);
	}
	void upd(int i) {
		if (i >= n) return;
		ll &t = val[i].tg;
		val[i<<1] += t, val[i<<1|1] += t;
		val[i] = node(val[i<<1], val[i<<1|1]);
	}
	pair<ll,ll> qmn(int l, int r) {
		l += n, r += n;
		for (int i = 19;i > 0;--i) upd(l>>i), upd(r>>i);
		pair<ll,ll> res {inf, n};
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) chmin(res, val[l++].get());
			if (r&1) chmin(res, val[--r].get());
		}
		assert(res.first < inf);
		return res;
	} 
};

// t1 for +
// t2 for -
struct bit { 
	int n;
	vector<ll> val;
	bit (int n) : n(n) {
		val.resize(n);
	}
	void add(int i, ll v) {
		for (;i < n;i += i&-i)
			val[i] += v;
	}
	ll qry(int i) {
		ll res = 0;
		for (;i;i^=i&-i) res += val[i];
		return res;
	}
	ll qry(int l, int r) { return qry(r) - qry(l-1); }
	int kth(ll k) {
		int res = 0;
		for (int i = 1<<19;i > 0;i>>=1) {
			if ((i|res) >= n || k <= val[res|i]) continue;
			assert(k > val[res|i]);
			k -= val[res|=i];
		}
		assert(k > 0);
		return res + 1; 
	} 
};

void solve() {

	sgt tree(q);
	bit t1(q + 10), t2(q + 10);

	for (int i = 1;i <= n;++i) {
		for (auto [j, d] : rec[i]) {
			tree.add(j, q, d);
			if (is_leave[j]) 
				t2.add(j, -d);
			else 
				t1.add(j, d);
		}

		for (auto [t, k] : allq[i]) {
			auto [v, p] = tree.qmn(0, t); 

			assert(p == 0 || is_leave[p]);

			assert(p < t);

			ll rk = t1.qry(p) + k + t2.qry(p+1, t);

			if (t1.qry(t) < rk) {
				res[t] = 0;
				continue;
			}
			
			int ind = t1.kth(rk);
			
			assert(ind < t);
			res[t] = ind >= t ? 0 : cid[ind]; 
		}
	} 
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> q; ++q;
	fill(res, res + q, -1);

	for (ll t, l, r, k, i = 1;i < q;++i) {
		cin >> t;
		if (t == 1) {
			cin >> l >> r >> cid[i] >> k;
			rec[l].pb(i, k);
			rec[r+1].pb(i,-k);
		}
		if (t == 2) {
			cin >> l >> r >> k;
			is_leave[i] = true;
			rec[l].pb(i, -k);
			rec[r+1].pb(i, k);
		}
		if (t == 3) {
			cin >> l >> k;
			allq[l].pb(i, k);
		}
	}

	solve();

	for (int i = 0;i < q;++i) {
		if (res[i] == -1) continue;
		cout << res[i] << '\n';
	}

} 
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 14540 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 14540 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 21928 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 576 ms 41088 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 14540 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 102 ms 20892 KB Output is correct
2 Correct 107 ms 21432 KB Output is correct
3 Correct 154 ms 21656 KB Output is correct
4 Correct 72 ms 19512 KB Output is correct
5 Correct 93 ms 20672 KB Output is correct
6 Correct 105 ms 21520 KB Output is correct
7 Correct 56 ms 19884 KB Output is correct
8 Correct 55 ms 19584 KB Output is correct
9 Correct 79 ms 20936 KB Output is correct
10 Correct 65 ms 19296 KB Output is correct
11 Correct 96 ms 21296 KB Output is correct
12 Correct 107 ms 21316 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 14540 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 14540 KB Output isn't correct
2 Halted 0 ms 0 KB -