oj.uz

답안 #670927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670927 2022-12-11T10:44:38 Z Kahou 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 1000 ms 132160 KB 
/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2.5e5 + 50;
ll n, m, q, out[N];
vector<pll> qr[N];
vector<pll> bd[N<<2];
vector<pair<ll, pll>> vc[N<<2];
pll fen[N];

void join(ll l, ll r, ll c, ll k, ll tim, ll u=1, ll tl=1, ll tr=n) {
	if (r < tl || tr < l) return;
	if (l <= tl && tr <= r) {
		vc[u].push_back({tim, {k, c}});
		return;
	}
	ll md = (tl+tr)/2;
	ll lc = u<<1;
	ll rc = u<<1|1;
	join(l, r, c, k, tim, lc, tl, md), join(l, r, c, k, tim, rc, md+1, tr);
}
void leave(ll l, ll r, ll k, ll tim, ll u=1, ll tl=1, ll tr=n) {
	if (r < tl || tr < l) return;
	if (l <= tl && tr <= r) {
		bd[u].push_back({tim, k});
		return;
	}
	ll md = (tl+tr)/2;
	ll lc = u<<1;
	ll rc = u<<1|1;
	leave(l, r, k, tim, lc, tl, md), leave(l, r, k, tim, rc, md+1, tr);
}
void service(ll id, ll x, ll tim, ll u=1, ll tl=1, ll tr=n) {
	if (id < tl || tr < id) return;
	if (tl == tr) {
		qr[tl].push_back({tim, x});
		return;
	}
	ll md = (tl+tr)/2;
	ll lc = u<<1;
	ll rc = u<<1|1;
	service(id, x, tim, lc, tl, md), service(id, x, tim, rc, md+1, tr);
}

void upd(ll i, ll x) {
	if (!i) return fen[i].F += x, void();
	for (; i < N; i += i&-i) {
		fen[i].F += x;
	}
}
ll get(ll x) {
	ll id = 0;
	x -= fen[0].F;
	for (ll k = 18; k >= 0; k--) {
		if (id+(1<<k) < N && fen[id^(1<<k)].F < x) {
			id ^= (1<<k);
			x -= fen[id].F;
		}
	}
	id++;
	return id;
}

void dfs(ll u=1, ll tl=1, ll tr=n) {
	for (pll x: bd[u]) {
		upd(0, x.S);
	}
	for (pair<ll, pll> x:vc[u]) {
		fen[x.F].S = x.S.S;
		upd(x.F, x.S.F);
	}
	if (tl == tr) {
		for (pll x:qr[tl]) {
			ll id = get(x.S);
			cerr << "OK " << x.F << ' ' << x.S << ' ' << id << endl;
			out[x.F] = (id < x.F? fen[id].S : 0);
		}
	}
	ll md = (tl+tr)/2;
	ll lc = u<<1;
	ll rc = u<<1|1;
	if (tl < tr) dfs(lc, tl, md), dfs(rc, md+1, tr);

	for (pair<ll, pll> x:vc[u]) {
		fen[x.F].S = 0;
		upd(x.F, -x.S.F);
	}
	reverse(bd[u].begin(), bd[u].end());
	for (pll x: bd[u]) {
		upd(0, x.S);
	}
}

void solve() {
	cin >> n >> m >> q;
	for (ll i = 1; i <= q; i++) {
		out[i] = -1;
		ll t, l, r, k, c, id, x;
		cin >> t;
		if (t == 1) {
			cin >> l >> r >> c >> k;
			join(l, r, c, k, i);
		}
		if (t == 2) {
			cin >> l >> r >> k;
			leave(l, r, k, i);
		}
		if (t == 3) {
			cin >> id >> x;
			service(id, x, i);
		}
	}
	dfs();
	for (ll i = 1; i <= q; i++) {
		if (out[i] < 0) continue;
		cout << out[i] << endl;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 53460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 53460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 281 ms 64548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1092 ms 132160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 53460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 370 ms 70320 KB Output is correct
2 Correct 402 ms 71800 KB Output is correct
3 Correct 406 ms 72424 KB Output is correct
4 Correct 282 ms 67332 KB Output is correct
5 Correct 359 ms 70532 KB Output is correct
6 Correct 395 ms 73288 KB Output is correct
7 Correct 268 ms 58100 KB Output is correct
8 Correct 263 ms 57752 KB Output is correct
9 Correct 315 ms 59004 KB Output is correct
10 Correct 273 ms 68868 KB Output is correct
11 Correct 373 ms 75820 KB Output is correct
12 Correct 412 ms 75900 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 53460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 53460 KB Output isn't correct
2 Halted 0 ms 0 KB -