oj.uz

Submission #1089101

# Submission time Handle Problem Language Result Execution time Memory
1089101 2024-09-16T05:05:18 Z coldbr3w Food Court (JOI21_foodcourt) C++17
9 / 100
 1000 ms 80320 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll blocks = 350;
int n,m,q;
vector<pll>t[N], ask[N];
int g[N], res[N];
bool add[N], ok[N];
struct segment_tree_min{
    ll n;
    vector<pair<ll,ll>>st;
	vector<ll> lz;
    void init(int _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10);
        lz.clear(); lz.resize(4 * n + 10, 0);
		build(1,1,n);
    }
	void build(int id, int l, int r){
		if(l == r){
			st[id] = {0, l};
			return;
		}
		int mid = (l + r) / 2;
		build(2 * id, l, mid); build(2 * id + 1, mid + 1, r);
		st[id] = min(st[2 * id], st[2 * id + 1]);
	}
    void down(int id, int l, int r){
        st[id].F += lz[id];
        if(l != r) lz[2 * id] += lz[id], lz[2 * id + 1] += lz[id];
        lz[id] = 0;
    }
    void update(int id, int l, int r, int left, int right, ll val){
        down(id, l, r);
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            lz[id] += val;
            down(id, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = min(st[2 * id], st[2 * id + 1]);
    }
    pair<ll,ll> get(int id, int l, int r, int left, int right){
        down(id, l, r);
        if(l > right || r < left) return {inf, 0};
        if(left <= l && r <= right) return st[id];
        int mid = (l + r) / 2;
        return min(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    pll get(ll l, ll r){return get(1,1,n,l,r);}
} stmin;
struct segment_tree_sum{
	ll n;
    vector<ll>st, lz;
    void init(int _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, 0);
        lz.clear(); lz.resize(4 * n + 10, 0);
    }
    void down(int id, ll l, ll r){
        st[id] += lz[id] * (r - l + 1);
        if(l != r) lz[2 * id] += lz[id], lz[2 * id + 1] += lz[id];
        lz[id] = 0;
    }
    void update(int id, int l, int r, int left, int right, ll val){
        down(id, l, r);
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            lz[id] += val;
            down(id, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = st[2 * id] + st[2 * id + 1];
    }
    ll get(int id, int l, int r, int left, int right){
        down(id, l, r);
        if(l > right || r < left) return 0;
        if(left <= l && r <= right) return st[id];
        int mid = (l + r) / 2;
        return get(2 * id, l, mid, left, right) + get(2 * id + 1, mid + 1, r, left, right);
    }
	int walk(int id, int l, int r, int pos, int val){
		down(id, l, r);
		if(r < pos || st[id] < val) return -1;
		if(l == r) return l;
		int mid = (l + r) / 2;
		int res = -1;
		down(2 * id, l, mid); down(2 * id + 1, mid + 1, r);
		if(st[2 * id] >= val) res = walk(2 * id, l, mid, pos, val);
		if(res == -1) res = walk(2 * id + 1, mid + 1, r, pos, val);
		return res;
	}
	int walk(int pos, int val){return walk(1,1,n,pos,val);}
    void update(int l, int r, ll val){update(1,1,n,l,r,val);}
    ll get(int l, int r){return get(1,1,n,l,r);}
} st1, st2;
void to_thic_cau(){
	cin >> n >> m >> q;
	st1.init(q); st2.init(q); stmin.init(q);
	for(int i = 1; i <= q;i++){
		int typ; cin >> typ;
		if(typ == 1){
			int l,r,c; ll k; cin >> l >> r >> c >> k;
			g[i] = c; add[i] = 1;
			t[l].pb({i, k}); t[r + 1].pb({i, -k});
		}
		else if(typ == 2){
			int l,r; ll k; cin >> l >> r >> k;
			t[l].pb({i, -k}); t[r+1].pb({i, k});
		}
		else{
			ok[i] = 1;
			ll a,b; cin >> a >> b;
			ask[a].pb({b, i});
		}
	}	
	for(int i = 1; i <= n;i++){
		for(auto x : t[i]){
			int j = x.F; ll k = x.S;
			stmin.update(j, q, k);
			if(add[j]) st1.update(j, q, k); 
			else st2.update(j, q, -k);
		}
		for(auto x : ask[i]){
			ll v = x.F, j = x.S;
			pair<ll,int> cur = min(make_pair(0ll,0ll), stmin.get(1, j));
			if(stmin.get(j, j).F < cur.F + v) continue;
			v += st2.get(j, j) + cur.F;
			res[j] = g[st1.walk(cur.S + 1, v)];	
		}
	}
	for(int i = 1; i <= q;i++) if(ok[i]) cout << res[i] << " ";
	cout << '\n';
}
 
signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14936 KB Output is correct
2 Correct 10 ms 14940 KB Output is correct
3 Correct 9 ms 14896 KB Output is correct
4 Correct 10 ms 14940 KB Output is correct
5 Correct 9 ms 14940 KB Output is correct
6 Correct 9 ms 14936 KB Output is correct
7 Correct 9 ms 14940 KB Output is correct
8 Correct 14 ms 15148 KB Output is correct
9 Correct 11 ms 14940 KB Output is correct
10 Correct 15 ms 15016 KB Output is correct
11 Correct 9 ms 14940 KB Output is correct
12 Correct 9 ms 14940 KB Output is correct
13 Correct 9 ms 15208 KB Output is correct
14 Correct 10 ms 14940 KB Output is correct
15 Correct 8 ms 14940 KB Output is correct
16 Correct 9 ms 14940 KB Output is correct
17 Correct 8 ms 14940 KB Output is correct
18 Correct 9 ms 14940 KB Output is correct
19 Correct 9 ms 14920 KB Output is correct
20 Correct 9 ms 15160 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14936 KB Output is correct
2 Correct 10 ms 14940 KB Output is correct
3 Correct 9 ms 14896 KB Output is correct
4 Correct 10 ms 14940 KB Output is correct
5 Correct 9 ms 14940 KB Output is correct
6 Correct 9 ms 14936 KB Output is correct
7 Correct 9 ms 14940 KB Output is correct
8 Correct 14 ms 15148 KB Output is correct
9 Correct 11 ms 14940 KB Output is correct
10 Correct 15 ms 15016 KB Output is correct
11 Correct 9 ms 14940 KB Output is correct
12 Correct 9 ms 14940 KB Output is correct
13 Correct 9 ms 15208 KB Output is correct
14 Correct 10 ms 14940 KB Output is correct
15 Correct 8 ms 14940 KB Output is correct
16 Correct 9 ms 14940 KB Output is correct
17 Correct 8 ms 14940 KB Output is correct
18 Correct 9 ms 14940 KB Output is correct
19 Correct 9 ms 14920 KB Output is correct
20 Correct 9 ms 15160 KB Output is correct
21 Incorrect 9 ms 15080 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 32684 KB Output is correct
2 Correct 103 ms 32948 KB Output is correct
3 Correct 120 ms 32852 KB Output is correct
4 Correct 92 ms 32848 KB Output is correct
5 Correct 97 ms 32952 KB Output is correct
6 Correct 90 ms 32868 KB Output is correct
7 Correct 50 ms 30668 KB Output is correct
8 Correct 54 ms 31176 KB Output is correct
9 Correct 99 ms 32852 KB Output is correct
10 Correct 94 ms 32776 KB Output is correct
11 Correct 94 ms 32852 KB Output is correct
12 Correct 107 ms 32788 KB Output is correct
13 Correct 85 ms 31312 KB Output is correct
14 Correct 91 ms 33088 KB Output is correct
15 Correct 100 ms 33064 KB Output is correct
16 Correct 113 ms 33364 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 482 ms 80320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14936 KB Output is correct
2 Correct 10 ms 14940 KB Output is correct
3 Correct 9 ms 14896 KB Output is correct
4 Correct 10 ms 14940 KB Output is correct
5 Correct 9 ms 14940 KB Output is correct
6 Correct 9 ms 14936 KB Output is correct
7 Correct 9 ms 14940 KB Output is correct
8 Correct 14 ms 15148 KB Output is correct
9 Correct 11 ms 14940 KB Output is correct
10 Correct 15 ms 15016 KB Output is correct
11 Correct 9 ms 14940 KB Output is correct
12 Correct 9 ms 14940 KB Output is correct
13 Correct 9 ms 15208 KB Output is correct
14 Correct 10 ms 14940 KB Output is correct
15 Correct 8 ms 14940 KB Output is correct
16 Correct 9 ms 14940 KB Output is correct
17 Correct 8 ms 14940 KB Output is correct
18 Correct 9 ms 14940 KB Output is correct
19 Correct 9 ms 14920 KB Output is correct
20 Correct 9 ms 15160 KB Output is correct
21 Correct 95 ms 32684 KB Output is correct
22 Correct 103 ms 32948 KB Output is correct
23 Correct 120 ms 32852 KB Output is correct
24 Correct 92 ms 32848 KB Output is correct
25 Correct 97 ms 32952 KB Output is correct
26 Correct 90 ms 32868 KB Output is correct
27 Correct 50 ms 30668 KB Output is correct
28 Correct 54 ms 31176 KB Output is correct
29 Correct 99 ms 32852 KB Output is correct
30 Correct 94 ms 32776 KB Output is correct
31 Correct 94 ms 32852 KB Output is correct
32 Correct 107 ms 32788 KB Output is correct
33 Correct 85 ms 31312 KB Output is correct
34 Correct 91 ms 33088 KB Output is correct
35 Correct 100 ms 33064 KB Output is correct
36 Correct 113 ms 33364 KB Output is correct
37 Execution timed out 1026 ms 31056 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 31316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14936 KB Output is correct
2 Correct 10 ms 14940 KB Output is correct
3 Correct 9 ms 14896 KB Output is correct
4 Correct 10 ms 14940 KB Output is correct
5 Correct 9 ms 14940 KB Output is correct
6 Correct 9 ms 14936 KB Output is correct
7 Correct 9 ms 14940 KB Output is correct
8 Correct 14 ms 15148 KB Output is correct
9 Correct 11 ms 14940 KB Output is correct
10 Correct 15 ms 15016 KB Output is correct
11 Correct 9 ms 14940 KB Output is correct
12 Correct 9 ms 14940 KB Output is correct
13 Correct 9 ms 15208 KB Output is correct
14 Correct 10 ms 14940 KB Output is correct
15 Correct 8 ms 14940 KB Output is correct
16 Correct 9 ms 14940 KB Output is correct
17 Correct 8 ms 14940 KB Output is correct
18 Correct 9 ms 14940 KB Output is correct
19 Correct 9 ms 14920 KB Output is correct
20 Correct 9 ms 15160 KB Output is correct
21 Incorrect 9 ms 15080 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14936 KB Output is correct
2 Correct 10 ms 14940 KB Output is correct
3 Correct 9 ms 14896 KB Output is correct
4 Correct 10 ms 14940 KB Output is correct
5 Correct 9 ms 14940 KB Output is correct
6 Correct 9 ms 14936 KB Output is correct
7 Correct 9 ms 14940 KB Output is correct
8 Correct 14 ms 15148 KB Output is correct
9 Correct 11 ms 14940 KB Output is correct
10 Correct 15 ms 15016 KB Output is correct
11 Correct 9 ms 14940 KB Output is correct
12 Correct 9 ms 14940 KB Output is correct
13 Correct 9 ms 15208 KB Output is correct
14 Correct 10 ms 14940 KB Output is correct
15 Correct 8 ms 14940 KB Output is correct
16 Correct 9 ms 14940 KB Output is correct
17 Correct 8 ms 14940 KB Output is correct
18 Correct 9 ms 14940 KB Output is correct
19 Correct 9 ms 14920 KB Output is correct
20 Correct 9 ms 15160 KB Output is correct
21 Incorrect 9 ms 15080 KB Output isn't correct
22 Halted 0 ms 0 KB -