oj.uz

답안 #490384

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490384 2021-11-27T10:41:11 Z Asymmetry 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 778 ms 109660 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);
	}
};

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

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

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 53352 KB Output is correct
2 Correct 196 ms 53964 KB Output is correct
3 Correct 237 ms 54164 KB Output is correct
4 Correct 125 ms 36028 KB Output is correct
5 Correct 197 ms 53508 KB Output is correct
6 Correct 215 ms 54132 KB Output is correct
7 Correct 49 ms 18856 KB Output is correct
8 Correct 43 ms 19248 KB Output is correct
9 Correct 102 ms 36840 KB Output is correct
10 Correct 123 ms 52144 KB Output is correct
11 Correct 169 ms 53520 KB Output is correct
12 Correct 151 ms 53480 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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