Submission #490350

#	Time	Username	Problem	Language	Result	Execution time	Memory
490350		Asymmetry	Food Court (JOI21_foodcourt)	C++17	13 / 100	300 ms	70660 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);
	}
};

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);
			customers.Insert(ile, a, b, d);
			++ile;
			zap[ile] = c;
		}
		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:108:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%d", &a);
      |   ~~~~~^~~~~~~~~~
foodcourt.cpp:114:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |    scanf("%d%d%d%d", &a, &b, &c, &d);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:120:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |    scanf("%d%d%d", &a, &b, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:124:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |    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: 13 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11