Submission #490427

#	Time	Username	Problem	Language	Result	Execution time	Memory
490427		Asymmetry	Food Court (JOI21_foodcourt)	C++17	100 / 100	487 ms	68060 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 SegTreeFind {
	
	int com;
	vector <long long> st;
	
	SegTreeFind(int n) {
		com = 1;
		while (com < n) {
			com <<= 1;
		}
		st.resize(com << 1);
		--com;
	}
	
	void Insert(int x, int w) {
		x += com;
		st[x] = w;
		x >>= 1;
		while (x) {
			st[x] = st[x * 2] + st[x * 2 + 1];
			x >>= 1;
		}
	}
	
	int SubFind(int x, int l, int r, long long w) {
		if (l == r) {
			return l;
		}
		if (st[x * 2] >= w) {
			return SubFind(x * 2, l, (l + r) / 2, w);
		}
		return SubFind(x * 2 + 1, (l + r) / 2 + 1, r, w - st[x * 2]);
	}
	
	int Find(long long w) {
		if (st[1] < w) {
			return -1;
		}
		return SubFind(1, 1, com + 1, w);
	}
};

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;
long long war[N];
long long wej[N][5];
vector <pair <int, int> > v[N], vv[N];
vector <int> que[N];
int odp[N];

int main() {
	scanf("%d%d%d", &n, &m, &q);
	
	SegTreePlus off(n);
	
	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});
			vv[wej[i][1]].push_back({i, wej[i][4]});
			vv[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});
			off.Insert(wej[i][1], wej[i][2], wej[i][3]);
		}
		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);
			war[i] += wej[i][2] + off.Query(wej[i][1]);
		}
	}
	
	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);
		}
	}
	
	SegTreeFind customers(q);
	
	for (int i = 1; i <= n; ++ i) {
		for (auto j : vv[i]) {
			customers.Insert(j.first, j.second);
		}
		for (int j : que[i]) {
			odp[j] = customers.Find(war[j]);
			if (odp[j] > j) {
				odp[j] = -1;
			}
		}
	}
	
	for (int i = 1; i <= q; ++i) {
		if (odp[i] == 0) {
			continue;
		}
		if (odp[i] == -1) {
			printf("0\n");
			continue;
		}
		printf("%lld\n", wej[odp[i]][3]);
	}
	
	return 0;
}

Compilation message (stderr)

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

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