Submission #490384

#	Time	Username	Problem	Language	Result	Execution time	Memory
490384		Asymmetry	Food Court (JOI21_foodcourt)	C++17	13 / 100	778 ms	109660 KiB

foodcourt

//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>

using namespace std;

struct SegTreePlus {
	
	int com;
	vector <long long> st;
	
	SegTreePlus(int n) {
		com = 1;
		while (com < n) {
			com <<= 1;
		}
		st.resize(com << 1);
		--com;
	}
	
	void Insert(int a, int b, int w) {
		a += com;
		b += com;
		while (a <= b) {
			if (a&1) {
				st[a++] += w;
			}
			if (!(b&1)) {
				st[b--] += w;
			}
			a >>= 1;
			b >>= 1;
		}
	}
	
	long long Query(int x) {
		x += com;
		long long ret = 0;
		while (x) {
			ret += st[x];
			x >>= 1;
		}
		return ret;
	}
};

struct PerSegTreePlus {
	
	struct node {
		int l, r;
		long long w;
	};
	
	int com;
	vector <node> st;
	vector <int> day;
	
	PerSegTreePlus(int n) {
		com = 1;
		while (com < n) {
			com <<= 1;
		}
		st.resize(1);
		day.resize(1);
	}
	
	int SubInsert(int x, int l, int r, int ll, int rr, int w) {
		if (r < ll || rr < l) {
			return x;
		}
		if (ll <= l && r <= rr) {
			st.push_back({st[x].l, st[x].r, st[x].w+w});
			return st.size() - 1;
		}
		st.push_back(st[x]);
		x = st.size() - 1;
		int y = SubInsert(st[x].l, l, (l + r) / 2, ll, rr, w);
		st[x].l = y;
		y = SubInsert(st[x].r, (l + r) / 2 + 1, r, ll, rr, w);
		st[x].r = y;
		return x;
	}
	
	long long SubQuery(int x, int l, int r, int p) {
		if (l == r) {
			return st[x].w;
		}
		if (p <= (l + r) / 2) {
			return st[x].w + SubQuery(st[x].l, l, (l + r) / 2, p);
		}
		return st[x].w + SubQuery(st[x].r, (l + r) / 2 + 1, r, p);
	}
	
	void Insert(int x, int l, int r, int w) {
		day.push_back(SubInsert(day[x], 1, com, l, r, w));
	}
	
	long long Query(int x, int p) {
		return SubQuery(day[x], 1, com, p);
	}
};

struct SegTreeMerge {
	
	struct node {
		long long off, out;
	};
	
	int com;
	vector <node> st;
	
	SegTreeMerge(int n) {
		com = 1;
		while (com < n) {
			com <<= 1;
		}
		st.resize(com << 1);
		--com;
	}
	
	node merge(node p, node q) {
		if (p.out >= q.off) {
			return {p.off, p.out - q.off + q.out};
		}
		return {p.off + q.off - p.out, q.out};
	}
	
	void Insert(int x, int w) {
		x += com;
		if (w < 0) {
			st[x] = {-w, 0};
		}
		else {
			st[x] = {0, w};
		}
		x >>= 1;
		while (x) {
			st[x] = merge(st[x * 2], st[x * 2 + 1]);
			x >>= 1;
		}
	}
	
	long long Query(int a, int b) {
		a += com;
		b += com;
		node ret = {0, 0};
		vector <int> rg;
		while (a <= b) {
			if (a&1) {
				ret = merge(ret, st[a]);
				++a;
			}
			if (!(b&1)) {
				rg.push_back(b);
				--b;
			}
			a >>= 1;
			b >>= 1;
		}
		reverse(rg.begin(), rg.end());
		for (int i : rg) {
			ret = merge(ret, st[i]);
		}
		return ret.off;
	}
};

const int N = 251'000;
int n, m, q, a, b, c, d, ile;
long long war[N];
long long wej[N][5];
int zap[N]; // z jakiej grupy byli dodani ludzie w tym dodaniu;
vector <pair <int, int> > v[N];
vector <int> que[N];

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= q; ++i) {
		scanf("%lld", &wej[i][0]);
		if (wej[i][0] == 1) { // dodanie d ludzi na przedziale od a do b z grupy c
			scanf("%lld%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3], &wej[i][4]);
			v[wej[i][1]].push_back({i, wej[i][4]});
			v[wej[i][2] + 1].push_back({i, 0});
		}
		else if (wej[i][0] == 2) { // zabranie c ludzi z przedziału od a do b
			scanf("%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3]);
			v[wej[i][1]].push_back({i, -wej[i][3]});
			v[wej[i][2] + 1].push_back({i, 0});
		}
		else { // pytanie o a-tą pozycję i p-tą osobę
			scanf("%lld%lld", &wej[i][1], &wej[i][2]);
			que[wej[i][1]].push_back(i);
		}
	}
	
	SegTreeMerge eat(q);
	
	for (int i = 1; i <= n; ++i) {
		for (auto j : v[i]) {
			eat.Insert(j.first, j.second);
		}
		for (int j : que[i]) {
			war[j] = eat.Query(1, j);
		}
	}
	
	SegTreePlus off(n);
	PerSegTreePlus customers(n);
	
	for (int i = 1; i <= q; ++i) {
		if (wej[i][0] == 1) { // dodanie d ludzi na przedziale od a do b z grupy c
			customers.Insert(ile, wej[i][1], wej[i][2], wej[i][4]);
			++ile;
			zap[ile] = wej[i][3];
		}
		else if (wej[i][0] == 2) { // zabranie c ludzi z przedziału od a do b
			off.Insert(wej[i][1], wej[i][2], wej[i][3]);
		}
		else { // pytanie o a-tą pozycję i p-tą osobę
			long long p = wej[i][2] + off.Query(a) - war[i];
			a = wej[i][1];
			if (customers.Query(ile, a) < p) { // nie ma tylu ludzi
				printf("0\n");
				continue;
			}
			int bp = 0, bk = ile, bs;
			while (bk - bp > 1) {
				bs = (bp + bk) / 2;
				if (customers.Query(bs, a) < p) {
					bp = bs;
				}
				else {
					bk = bs;
				}
			}
			printf("%d\n", zap[bk]);
		}
	}
	return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:176:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |   scanf("%lld", &wej[i][0]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:180:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |    scanf("%lld%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3], &wej[i][4]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:185:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |    scanf("%lld%lld%lld", &wej[i][1], &wej[i][2], &wej[i][3]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:190:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |    scanf("%lld%lld", &wej[i][1], &wej[i][2]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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