Submission #425967

# Submission time Handle Problem Language Result Execution time Memory
425967 2021-06-13T12:36:56 Z Kevin_Zhang_TW Food Court (JOI21_foodcourt) C++17
13 / 100
537 ms 42736 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;

#define int ll

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

bool is_leave[MAX_N];

//          position, delta
vector<pair<int,int>> 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());
		}
		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];
		}
		return res + 1; 
	} 
};

void solve() {

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

	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]);

			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);
			//DE(t, k, v, p, rk, ind, cid[ind]);
			//DE(t1.qry(ind), rk, t1.qry(ind+1));
			
			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 106 ms 22344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 537 ms 42736 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 99 ms 21256 KB Output is correct
2 Correct 122 ms 21988 KB Output is correct
3 Correct 106 ms 22084 KB Output is correct
4 Correct 76 ms 19800 KB Output is correct
5 Correct 115 ms 21112 KB Output is correct
6 Correct 114 ms 22084 KB Output is correct
7 Correct 57 ms 20448 KB Output is correct
8 Correct 58 ms 19980 KB Output is correct
9 Correct 79 ms 21432 KB Output is correct
10 Correct 74 ms 19652 KB Output is correct
11 Correct 123 ms 21684 KB Output is correct
12 Correct 127 ms 21828 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 -