oj.uz

답안 #426023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426023 2021-06-13T13:02:48 Z Kevin_Zhang_TW 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 245 ms 82864 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);
			if (a.mn == mn) pos = a.pos;
			else 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 add(int l, int r, ll v) {
		int sl = l+=n, sr = r+=n;
		for (int i = 19;i >= 0;--i) push(l>>i), push(r>>i);
		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 push(int i) {
		if (i >= n) return;
		ll &t = val[i].tg;
		val[i<<1] += t, val[i<<1|1] += t;
		t = 0;
	}
	void upd(int i) {
		if (i >= n) return;
		push(i);
		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) push(l>>i), push(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; 
	} 
};

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 28 ms 29380 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 20884 KB Output is correct
2 Correct 162 ms 21524 KB Output is correct
3 Correct 172 ms 21632 KB Output is correct
4 Correct 115 ms 19568 KB Output is correct
5 Correct 104 ms 20680 KB Output is correct
6 Correct 166 ms 21528 KB Output is correct
7 Correct 65 ms 19928 KB Output is correct
8 Correct 63 ms 19596 KB Output is correct
9 Correct 88 ms 20916 KB Output is correct
10 Correct 91 ms 19412 KB Output is correct
11 Correct 135 ms 21176 KB Output is correct
12 Correct 112 ms 21324 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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