Submission #490345

#	Time	Username	Problem	Language	Result	Execution time	Memory
490345		Asymmetry	Food Court (JOI21_foodcourt)	C++17	0 / 100	131 ms	18740 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 0;
		}
		if (ll <= l || r <= rr) {
			st.push_back({0, 0, st[x].w+w});
			return st.size() - 1;
		}
		st.push_back(st[x]);
		x = st.size() - 1;
		st[x].l = SubInsert(st[x].l, l, (l + r) / 2, ll, rr, w);
		st[x].r = SubInsert(st[x].r, (l + r) / 2 + 1, r, ll, rr, w);
		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);
	}
};

const int N = 251'000;
int n, m, q, a, b, c, d, ile;
int zap[N]; // z jakiej grupy byli dodani ludzie w tym dodaniu;
long long p;

int main() {
	scanf("%d%d%d", &n, &m, &q);
	SegTreePlus off(n);
	PerSegTreePlus customers(n);
	for (int i = 1; i <= q; ++i) {
		scanf("%d", &a);
		if (a == 1) { // dodanie d ludzi na przedziale od a do b z grupy c
			scanf("%d%d%d%d", &a, &b, &c, &d);
			zap[i] = c;
			customers.Insert(ile, a, b, d);
			++ile;
		}
		else if (a == 2) { // zabranie c ludzi z przedziału od a do b
			scanf("%d%d%d", &a, &b, &c);
			off.Insert(a, b, c);
		}
		else { // pytanie o a-tą pozycję i p-tą osobę
			scanf("%d%lld", &a, &p);
			p += off.Query(a);
			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:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   scanf("%d", &a);
      |   ~~~~~^~~~~~~~~~
foodcourt.cpp:112:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |    scanf("%d%d%d%d", &a, &b, &c, &d);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:118:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |    scanf("%d%d%d", &a, &b, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:122:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |    scanf("%d%lld", &a, &p);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

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