Submission #1288747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288747		thieunguyenhuy	Food Court (JOI21_foodcourt)	C++20	27 / 100	1098 ms	151128 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2> bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T> void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long random(long long l, long long r) {
    return uniform_int_distribution<long long>(l, r)(rng);
}
unsigned long long random(unsigned long long l, unsigned long long r) {
    return uniform_int_distribution<unsigned long long>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 25e4 + 5, LG = 19;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;

int n, m, q;

namespace STB { // segment tree beats
    // struct Node {
    //     ll sum, lazy;
    //     ll max1, max2, max_cnt;
    //     ll min1, min2, min_cnt;

    //     Node() {
    //     	sum = lazy = 0;
    //     	max1 = max2 = max_cnt = 0;
    //     	min1 = min2 = min_cnt = 0;
    //     }
    // } nodes[N * 4];

    // void push_up(int id) {
    //     nodes[id].sum = nodes[id << 1].sum + nodes[id << 1 | 1].sum;
    //     nodes[id].max_cnt = nodes[id].min_cnt = 0;

    //     nodes[id].max1 = max(nodes[id << 1].max1, nodes[id << 1 | 1].max1);
    //     if (nodes[id].max1 == nodes[id << 1].max1)
    //         nodes[id].max_cnt += nodes[id << 1].max_cnt;
    //     if (nodes[id].max1 == nodes[id << 1 | 1].max1)
    //         nodes[id].max_cnt += nodes[id << 1 | 1].max_cnt;
    //     vector<ll> ve1{nodes[id << 1].max1, nodes[id << 1].max2, nodes[id << 1 | 1].max1, nodes[id << 1 | 1].max2};
    //     sort (ve1.begin(), ve1.end(), greater<ll>());
    //     for (auto &x : ve1) if (x != nodes[id].max1) {
    //         nodes[id].max2 = x;
    //         break;
    //     }

    //     nodes[id].min1 = min(nodes[id << 1].min1, nodes[id << 1 | 1].min1);
    //     if (nodes[id].min1 == nodes[id << 1].min1)
    //         nodes[id].min_cnt += nodes[id << 1].min_cnt;
    //     if (nodes[id].min1 == nodes[id << 1 | 1].min1)
    //         nodes[id].min_cnt += nodes[id << 1 | 1].min_cnt;
    //     vector<ll> ve2{nodes[id << 1].min1, nodes[id << 1].min2, nodes[id << 1 | 1].min1, nodes[id << 1 | 1].min2};
    //     sort (ve2.begin(), ve2.end());
    //     for (auto &x : ve2) if (x != nodes[id].min1) {
    //         nodes[id].min2 = x;
    //         break;
    //     }
    // }

    // void push_add(int id, int l, int r, ll val) {
    //     if (val == 0) return;
    //     nodes[id].sum += (r - l + 1) * val, nodes[id].lazy += val;
    //     nodes[id].max1 += val, nodes[id].min1 += val;
    //     if (nodes[id].max2 != -INF) nodes[id].max2 += val;
    //     if (nodes[id].min2 != INF) nodes[id].min2 += val;
    // }

    // void push_max(int id, int l, int r, ll val) {
    //     if (val >= nodes[id].max1) return;
    //     nodes[id].sum -= nodes[id].max1 * nodes[id].max_cnt;
    //     nodes[id].max1 = val;
    //     nodes[id].sum += nodes[id].max1 * nodes[id].max_cnt;
    //     if (l == r) nodes[id].min1 = nodes[id].max1;
    //     else if (!minimize(nodes[id].min1, val)) minimize(nodes[id].min2, val);
    // }

    // void push_min(int id, int l, int r, ll val) {
    //     if (val <= nodes[id].min1) return;
    //     nodes[id].sum -= nodes[id].min1 * nodes[id].min_cnt;
    //     nodes[id].min1 = val;
    //     nodes[id].sum += nodes[id].min1 * nodes[id].min_cnt;
    //     if (l == r) nodes[id].max1 = nodes[id].min1;
    //     else if (!maximize(nodes[id].max1, val)) maximize(nodes[id].max2, val);
    // }

    // void down(int id, int l, int r) {
    //     if (l == r) return;

    //     int mid = (l + r) >> 1;
    //     push_add(id << 1, l, mid, nodes[id].lazy);
    //     push_add(id << 1 | 1, mid + 1, r, nodes[id].lazy);

    //     push_max(id << 1, l, mid, nodes[id].max1);
    //     push_max(id << 1 | 1, mid + 1, r, nodes[id].max1);

    //     push_min(id << 1, l, mid, nodes[id].min1);
    //     push_min(id << 1 | 1, mid + 1, r, nodes[id].min1);

    //     nodes[id].lazy = 0;
    // }

    // void update(int id, int l, int r, int u, int v, ll val) {
    //     if (l > v || r < u) return;
    //     if (u <= l && r <= v) {
    //         push_add(id, l, r, val);
    //         return;
    //     }
    //     down(id, l, r); int mid = (l + r) >> 1;
    //     update(id << 1, l, mid, u, v, val);
    //     update(id << 1 | 1, mid + 1, r, u, v, val);
    //     push_up(id);
    // }

    // void update(int u, int v, ll val) {
    //     update(1, 1, n, u, v, val);
    // }

    // void maximize(int id, int l, int r, int u, int v, int val) {
    //     if (l > v || r < u || val <= nodes[id].min1) return;
    //     if (u <= l && r <= v && val < nodes[id].min2) {
    //         push_min(id, l, r, val);
    //         return;
    //     }
    //     down(id, l, r); int mid = (l + r) >> 1;
    //     maximize(id << 1, l, mid, u, v, val);
    //     maximize(id << 1 | 1, mid + 1, r, u, v, val);
    //     push_up(id);
    // }

    // void maximize(int u, int v, int val) {
    //     maximize(1, 1, n, u, v, val);
    // }

    // ll get(int id, int l, int r, int u, int v) {
    //     if (l > v || r < u) return 0;
    //     if (u <= l && r <= v) return nodes[id].sum;
    //     down(id, l, r); int mid = (l + r) >> 1;
    //     return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    // }

    // ll get(int u, int v) {
    //     return get(1, 1, n, u, v);
    // }

    ll a[N];

    void update(int l, int r, int val) {
    	for (int i = l; i <= r; ++i) a[i] += val;
    }

    void maximize(int l, int r, int val) {
    	for (int i = l; i <= r; ++i) a[i] = max(a[i], 0ll + val);
    }

    ll get(int l, int r) {
    	ll sum = 0;
    	for (int i = l; i <= r; ++i) sum += a[i];
    	return sum;
    }
};

struct Node {
	int le, ri;
	ll sum;

	Node(ll value = 0) {
		le = ri = 0;
		sum = value;
	}
} nodes[2 * N * LG];
int numNode = 0;
vector<int> version;

struct PersistentIT {
	int n;

	PersistentIT(int _n = 0) {
		n = _n;
	}

	int update(int oldId, int l, int r, int p, int val) {
		if (l > p || r < p) return oldId;

		int id = ++numNode;
		if (l == r) {
			nodes[id] = nodes[oldId];
			nodes[id].sum += val;
			return id;
		}

		int mid = (l + r) >> 1;
		nodes[id].le = update(nodes[oldId].le, l, mid, p, val);
		nodes[id].ri = update(nodes[oldId].ri, mid + 1, r, p, val);

		nodes[id].sum = nodes[nodes[id].le].sum + nodes[nodes[id].ri].sum;
		return id;
	}

	int update(int root, int p, int val) {
		return update(root, 1, n, p, val);
	}

	int update(int root, int l, int r, int val) {
		root = update(root, l, val);
		return update(root, r + 1, -val);
	}

	ll get(int id, int l, int r, int u, int v) {
		if (l > v || r < u) return 0;
		if (u <= l && r <= v) return nodes[id].sum;
		int mid = (l + r) >> 1;
		return get(nodes[id].le, l, mid, u, v) + get(nodes[id].ri, mid + 1, r, u, v);
	}

	ll get(int root, int p) {
		return get(root, 1, n, 1, p);
	}
};

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> q;

    PersistentIT R(n);

    version.emplace_back(0);
    vector<int> colors = {0};

    for (int i = 1; i <= q; ++i) {
    	int type; cin >> type;
    	if (type == 1) {
    		int l, r, c, k; cin >> l >> r >> c >> k;
    		version.emplace_back(R.update(version.back(), l, r, k));
    		colors.emplace_back(c);
    		STB::update(l, r, k);
    	}
    	if (type == 2) {
    		int l, r, k; cin >> l >> r >> k;
    		STB::update(l, r, -k);
    		STB::maximize(l, r, 0);
    	}
    	if (type == 3) {
    		int x; ll k; cin >> x >> k;
    		ll len = STB::get(x, x), rightId = R.get(version.back(), x);
    		ll leftId = rightId - len;
    		if (leftId + k > rightId) cout << "0\n";
    		else {
    			// cerr << "hihi " << i << '\n';
    			int low = 1, high = version.size() - 1, p = -1;
    			while (low <= high) {
    				int mid = (low + high) >> 1;
    				if (R.get(version[mid], x) >= leftId + k) high = (p = mid) - 1;
    				else low = mid + 1;
    			}
    			assert(p != -1);
    			cout << colors[p] << '\n';
    			// cout << m << '\n';
    		} 
    	}
    }

    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 13 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11