oj.uz

답안 #681785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681785 2023-01-14T09:43:09 Z vjudge1 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 1000 ms 132040 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 31 ms 53472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 70384 KB Output is correct
2 Correct 392 ms 71892 KB Output is correct
3 Correct 410 ms 72360 KB Output is correct
4 Correct 285 ms 67412 KB Output is correct
5 Correct 388 ms 70580 KB Output is correct
6 Correct 411 ms 73252 KB Output is correct
7 Correct 284 ms 58088 KB Output is correct
8 Correct 277 ms 57720 KB Output is correct
9 Correct 379 ms 59040 KB Output is correct
10 Correct 271 ms 68868 KB Output is correct
11 Correct 384 ms 75916 KB Output is correct
12 Correct 384 ms 75960 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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