oj.uz

Submission #416252

# Submission time Handle Problem Language Result Execution time Memory
416252 2021-06-02T08:31:41 Z amoo_safar Food Court (JOI21_foodcourt) C++17
7 / 100
 1000 ms 41284 KB 
// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 25e4 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

typedef pll pii;

pii seg[N << 2]; // sum ans
pii nl = {0, 0};
pii Merge(pii A, pii B){
	return {A.F + B.F, min(A.S, A.F + B.S)};
}
void Apply(int id, pii X){
	seg[id] = Merge(seg[id], X);
}
void Shift(int id){
	Apply(id << 1, seg[id]);
	Apply(id << 1 | 1, seg[id]);
	seg[id] = nl;
}
void Add(int id, int l, int r, pii X, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		Apply(id, X);
		return ;
	}
	int mid = (L + R) >> 1;
	Shift(id);
	Add(id << 1, l, r, X, L, mid);
	Add(id<<1|1, l, r, X, mid, R);
}
pll Get(int id, int idx, int L, int R){
	if(L + 1 == R) return seg[id];
	int mid = (L + R) >> 1;
	Shift(id);
	if(idx < mid)
		return Get(id << 1, idx, L, mid);
	return Get(id << 1 | 1, idx, mid, R);
}

ll fen[N];
void Add(int idx, ll x){
	for(; idx < N; idx += idx & (-idx))
		fen[idx] += x;
}
ll Get(int idx){
	ll res = 0;
	for(; idx; idx -= idx & (-idx))
		res += fen[idx];
	return res;
}


int t[N];
ll a[N], b[N], c[N], d[N], ps[N];
int lf[N], rt[N];
vector<int> V[N];


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 1; i <= q; i++){
		cin >> t[i];
		if(t[i] == 1)
			cin >> a[i] >> b[i] >> c[i] >> d[i];
		if(t[i] == 2){
			cin >> a[i] >> b[i] >> c[i];
			Add(a[i], c[i]);
			Add(b[i] + 1, -c[i]);
		}
		if(t[i] == 3){
			cin >> a[i] >> b[i];
			lf[i] = -1;
			rt[i] = i + 1;
			ps[i] = Get(a[i]);
		}
	}
	for(int _ = 0; _ < 20; _++){
		// debug(_);
		for(int i = 1; i <= q; i++) V[i].clear();
		memset(fen, 0, sizeof fen);
		fill(seg, seg + (N << 2), nl);

		int mid;
		for(int i = 1; i <= q; i++){
			if(t[i] == 3 && lf[i] + 1 < rt[i]){
				// if(_>18) debug(_);
				mid = (lf[i] + rt[i]) >> 1;
				// debug(mid);
				V[mid].pb(i);
			}
		}

		for(int i = 1; i <= q; i++){
			// debug(i);
			if(t[i] == 1){
				Add(1, a[i], b[i] + 1, {d[i], 0}, 1, n + 1);
			} else if(t[i] == 2){
				Add(1, a[i], b[i] + 1, {-c[i], -c[i]}, 1, n + 1);
				
				Add(a[i], c[i]);
				Add(b[i] + 1, -c[i]);
			}
			for(int q_id : V[i]){
				pll res = Get(1, a[q_id], 1, n + 1);
				ll nw = res.F - res.S;
				ll dec = (ps[q_id] - Get(a[q_id]));
				assert(dec >= 0);
				nw -= dec; 
				if(nw >= b[q_id])
					rt[q_id] = i;
				else
					lf[q_id] = i;
			}
		}
	}
	for(int i = 1; i <= q; i++){
		if(t[i] != 3) continue;
		if(rt[i] == i + 1) cout << "0\n";
		else
			cout << c[rt[i]] << '\n';
	}
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23948 KB Output is correct
2 Correct 78 ms 23996 KB Output is correct
3 Incorrect 71 ms 23904 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23948 KB Output is correct
2 Correct 78 ms 23996 KB Output is correct
3 Incorrect 71 ms 23904 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 29156 KB Output is correct
2 Correct 710 ms 29224 KB Output is correct
3 Correct 773 ms 29160 KB Output is correct
4 Correct 722 ms 29168 KB Output is correct
5 Correct 715 ms 29288 KB Output is correct
6 Correct 745 ms 29108 KB Output is correct
7 Correct 174 ms 28808 KB Output is correct
8 Correct 172 ms 28848 KB Output is correct
9 Correct 748 ms 28888 KB Output is correct
10 Correct 793 ms 29084 KB Output is correct
11 Correct 750 ms 29076 KB Output is correct
12 Correct 742 ms 29252 KB Output is correct
13 Correct 555 ms 28632 KB Output is correct
14 Correct 653 ms 29156 KB Output is correct
15 Correct 563 ms 28936 KB Output is correct
16 Correct 606 ms 28996 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 41284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23948 KB Output is correct
2 Correct 78 ms 23996 KB Output is correct
3 Incorrect 71 ms 23904 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 28816 KB Output is correct
2 Correct 717 ms 29260 KB Output is correct
3 Correct 753 ms 29268 KB Output is correct
4 Correct 524 ms 27600 KB Output is correct
5 Correct 617 ms 28528 KB Output is correct
6 Correct 817 ms 29272 KB Output is correct
7 Correct 160 ms 28612 KB Output is correct
8 Correct 161 ms 28484 KB Output is correct
9 Incorrect 324 ms 29252 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23948 KB Output is correct
2 Correct 78 ms 23996 KB Output is correct
3 Incorrect 71 ms 23904 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23948 KB Output is correct
2 Correct 78 ms 23996 KB Output is correct
3 Incorrect 71 ms 23904 KB Output isn't correct
4 Halted 0 ms 0 KB -