oj.uz

답안 #426043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426043 2021-06-13T13:13:15 Z Kevin_Zhang_TW 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 262 ms 82800 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) {
			tg = 0;
			mn = min(a.mn, b.mn);
			pos = a.mn == mn ? a.pos : b.pos;
		}
		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 pa(int j) { for (int i = 19;i >= 0;--i) upd(j>>i); }
	void add(int l, int r, ll v) {
		assert(r == q);
		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;
		pa(l), pa(r);
		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; 
	} 
};
 
struct sss {
	vector<ll> val;
	int n;
	sss (int n) : n(n) {
		val.resize(n);
	}
	void add(int l, int r, ll v) {
		for (;l < r;++l)
			val[l] += v;
	}
	pair<ll,ll> qmn(int l, int r) {
		pair<ll,ll> res {inf, n};
		for (;l < r;++l)
			chmin(res, make_pair(val[l], (ll)l));
		return res;
	}
};
void solve() {
 
	//sss tree(q);
	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 {
				assert(cid[j]);
				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);
 
			//assert(p == 0 || t1.qry(p) == t1.qry(p-1));
 
			assert(t1.qry(p) - t2.qry(p) == v);
 
			if (t1.qry(t) < rk) {
				res[t] = 0;
				continue;
			}
			
			int ind = t1.kth(rk);
			
			assert(ind < t);
			res[t] = cid[ind]; 
 
			assert(cid[ind] >= 1 && cid[ind] <= m);
		}
	} 
}
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';
	}
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 29336 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 29336 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 72 ms 44220 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 262 ms 82800 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 29336 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 20892 KB Output is correct
2 Correct 113 ms 21524 KB Output is correct
3 Correct 122 ms 21652 KB Output is correct
4 Correct 93 ms 19572 KB Output is correct
5 Correct 106 ms 20616 KB Output is correct
6 Correct 135 ms 21632 KB Output is correct
7 Correct 66 ms 19924 KB Output is correct
8 Correct 58 ms 19648 KB Output is correct
9 Correct 91 ms 20916 KB Output is correct
10 Correct 77 ms 19424 KB Output is correct
11 Correct 97 ms 21240 KB Output is correct
12 Correct 141 ms 21244 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 29336 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 29336 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -