| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 494681 | blue | 푸드 코트 (JOI21_foodcourt) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
const int mx = 250'000;
const ll INF = 1'000'000'000'000'000'000LL;
vi L(1+mx), R(1+mx), C(1+mx), A(1+mx);
vll K(1+mx), B(1+mx);
vi T(1+mx);
vi st[1+mx], en[1+mx], qr[1+mx];
vi ans(1+mx, 0);
segtree st1[530'001];
struct segtree
{
int l;
int r;
pair<ll, int> mn;
pair<ll, int> mx;
ll lp = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree* parent = NULL;
segtree()
{
;
}
void build(int L, int R, segtree* par)
{
l = L;
r = R;
parent = par;
mn = {0, l};
mx = {0, l};
if(l == r) return;
int m = (l+r)/2;
left = st1[++ct];
right = st1[++ct];
left->build(l, m, this);
right->build(m+1, r, this);
}
segtree(int L, int R, segtree* par)
{
build(L, R, par);
}
void add(int L, int R, ll V)
{
if(r < L || R < l) return;
else if(L <= l && r <= R)
{
lp += V;
mn.first += V;
mx.first += V;
}
else
{
left->add(L, R, V);
right->add(L, R, V);
mn = min(left->mn, right->mn);
mn.first += lp;
mx = max(left->mx, right->mx);
mx.first += lp;
}
}
pair<ll, int> rangemin(int L, int R)
{
if(R < l || r < L) return {INF, -1};
else if(L <= l && r <= R) return mn;
else
{
auto res = min(left->rangemin(L, R), right->rangemin(L, R));
res.first += lp;
return res;
}
}
};
int locate(segtree& S, int L, ll V) //find the first position > L with a value >= V, or return -1 if it doesn't exist
{
segtree* pos = &S;
ll above_lp = 0;
while(!(pos->l == L && pos->r == L))
{
above_lp += pos->lp;
if(L <= (pos->l + pos->r)/2)
pos = pos->left;
else
pos = pos->right;
}
while(1)
{
if(pos->parent == NULL) return -1;
if(above_lp + pos->parent->right->mx.first >= V)
{
pos = pos->parent->right;
break;
}
pos = pos->parent;
above_lp -= pos->lp;
}
while(!(pos->l == pos->r))
{
above_lp += pos->lp;
if(above_lp + pos->left->mx.first >= V)
pos = pos->left;
else
pos = pos->right;
}
return pos->l;
}
struct BIT
{
int Z;
vll arr;
BIT()
{
;
}
BIT(int z)
{
Z = z;
arr = vll(1+z, 0);
}
void add(int i, ll v)
{
for(int j = i; j <= Z; j += j&-j)
arr[j] += v;
}
ll prefsum(int i)
{
ll ans = 0;
for(int j = i; j >= 1; j -= j&-j)
ans += arr[j];
return ans;
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, Q;
cin >> N >> M >> Q;
for(int j = 1; j <= Q; j++)
{
cin >> T[j];
if(T[j] == 1) cin >> L[j] >> R[j] >> C[j] >> K[j];
else if(T[j] == 2)
{
cin >> L[j] >> R[j] >> K[j];
K[j] *= -1;
}
else cin >> A[j] >> B[j];
if(T[j] <= 2)
{
st[L[j]].push_back(j);
en[R[j]].push_back(j);
}
else qr[A[j]].push_back(j);
}
vll S(1+Q, 0);
vi ans(1+Q, 0);
segtree ST(0, Q, NULL);
segtree ST_plus(0, Q, NULL);
BIT plus_sum(1+Q), minus_sum(1+Q);
for(int i = 1; i <= N; i++)
{
for(int o: st[i])
{
S[o] = K[o];
ST.add(o, Q, +K[o]);
if(K[o] < 0) minus_sum.add(o, -K[o]);
if(K[o] > 0) ST_plus.add(o, Q, +K[o]);
}
for(int q: qr[i])
{
int p = ST.rangemin(0, q-1).second;
ll min_sum = minus_sum.prefsum(q) - minus_sum.prefsum(p);
// cerr << "p = " << p << '\n';
// cerr << "total loss = " << minus_sum << '\n';
ll plus_sub = ST_plus.rangemin(p, p).first;
int lo = locate(ST_plus, p, min_sum + B[q] + plus_sub);
if(lo != -1 && lo <= q)
{
ans[q] = C[lo];
}
}
for(int o: en[i])
{
S[o] = 0;
ST.add(o, Q, -K[o]);
if(K[o] < 0) minus_sum.add(o, +K[o]);
if(K[o] > 0)
ST_plus.add(o, Q, -K[o]);
}
}
for(int q = 1; q <= Q; q++)
if(T[q] == 3)
cout << ans[q] << '\n';
// cout << '\n';
}