oj.uz

답안 #490350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490350 2021-11-27T09:58:02 Z Asymmetry 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 300 ms 70660 KB 
//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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 9736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 300 ms 70660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 34584 KB Output is correct
2 Correct 177 ms 35956 KB Output is correct
3 Correct 173 ms 35912 KB Output is correct
4 Correct 133 ms 18680 KB Output is correct
5 Correct 167 ms 35892 KB Output is correct
6 Correct 168 ms 35908 KB Output is correct
7 Correct 28 ms 2332 KB Output is correct
8 Correct 29 ms 2656 KB Output is correct
9 Correct 83 ms 19332 KB Output is correct
10 Correct 93 ms 35760 KB Output is correct
11 Correct 123 ms 35800 KB Output is correct
12 Correct 122 ms 35740 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -