oj.uz

답안 #426003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426003 2021-06-13T12:55:07 Z Kevin_Zhang_TW 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 251 ms 82812 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 {
				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 22 ms 29388 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 20816 KB Output is correct
2 Correct 134 ms 21464 KB Output is correct
3 Correct 105 ms 21528 KB Output is correct
4 Correct 77 ms 19532 KB Output is correct
5 Correct 95 ms 20656 KB Output is correct
6 Correct 141 ms 21632 KB Output is correct
7 Correct 59 ms 19896 KB Output is correct
8 Correct 55 ms 19604 KB Output is correct
9 Correct 78 ms 20940 KB Output is correct
10 Correct 79 ms 19396 KB Output is correct
11 Correct 98 ms 21256 KB Output is correct
12 Correct 100 ms 21320 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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