oj.uz

Submission #76082

# Submission time Handle Problem Language Result Execution time Memory
76082 2018-09-12T03:37:34 Z arock Seats (IOI18_seats) C++14
33 / 100
 1791 ms 80548 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

int H, W;
vector<int> R, C;

struct seg {
	int min, ans;
} tree[4 * 1000 * 1000];
vector<int> rev;
int lazy[4 * 1000 * 1000];

seg merge(seg a, seg b) {
	if (a.min < b.min) {
		return a;
	} else if(b.min < a.min) {
		return b;
	} else {
		return {a.min, a.ans + b.ans};
	}
}

seg build(int cur, int lo, int hi) {
	if (lo == hi) {
		return tree[cur] = {0, 1};
	}

	int lmid = (lo + hi) / 2, rmid = lmid + 1;
	return merge(build(cur << 1 | 0, lo, lmid),
		         build(cur << 1 | 1, rmid, hi));
}

void update(int l, int r, int delta, int cur, int lo, int hi) {

	if (lo == l && hi == r) {
		lazy[cur]     += delta;
		tree[cur].min += delta;
	} else {

		lazy[cur << 1 | 0] += lazy[cur];
		tree[cur << 1 | 0].min += lazy[cur];
		lazy[cur << 1 | 1] += lazy[cur];
		tree[cur << 1 | 1].min += lazy[cur];
		lazy[cur] = 0;

		int lmid = (lo + hi) / 2, rmid = lmid + 1;
		if (l <= lmid) {
			update(l, min(r, lmid), delta, cur << 1 | 0, lo, lmid);
		}
		if (r >= rmid) {
			update(max(l, rmid), r, delta, cur << 1 | 1, rmid, hi);
		}

		tree[cur] = merge(tree[cur << 1 | 0],
			              tree[cur << 1 | 1]);
	}
}

void update(int l, int r, int delta) {
	update(l + 1, r, delta, 1, 1, H * W);
}

void give_initial_chart(int HH, int WW, vector<int> RR, vector<int> CC) {

	H = HH, W = WW, R = RR, rev = CC;

	C.resize(H * W + 2);
	C[0] = H * W;
	for (int i = 0; i < H * W; i++) {
		C[rev[i] + 1] = i;
	}
	C[H * W + 1] = H * W;

	build(1, 1, H * W);

	for (int i = 0; i <= H * W; i++) {
		update(min(C[i], C[i + 1]), max(C[i], C[i + 1]), +1);
	}
}


int swap_seats(int a, int b) {

	int ta = a, tb = b;

	a = rev[a] + 1, b = rev[b] + 1;

	update(min(C[a], C[a - 1]), max(C[a], C[a - 1]), -1);
	update(min(C[a], C[a + 1]), max(C[a], C[a + 1]), -1);
	update(min(C[b], C[b - 1]), max(C[b], C[b - 1]), -1);
	update(min(C[b], C[b + 1]), max(C[b], C[b + 1]), -1);

	swap(C[a], C[b]);
	swap(rev[ta], rev[tb]);

	update(min(C[a], C[a - 1]), max(C[a], C[a - 1]), +1);
	update(min(C[a], C[a + 1]), max(C[a], C[a + 1]), +1);
	update(min(C[b], C[b - 1]), max(C[b], C[b - 1]), +1);
	update(min(C[b], C[b + 1]), max(C[b], C[b + 1]), +1);

	return tree[1].min == 2? tree[1].ans : 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 418 ms 80548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 80548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 80548 KB Output is correct
2 Correct 62 ms 80548 KB Output is correct
3 Correct 103 ms 80548 KB Output is correct
4 Correct 130 ms 80548 KB Output is correct
5 Correct 217 ms 80548 KB Output is correct
6 Correct 980 ms 80548 KB Output is correct
7 Correct 1085 ms 80548 KB Output is correct
8 Correct 943 ms 80548 KB Output is correct
9 Correct 1791 ms 80548 KB Output is correct
10 Correct 881 ms 80548 KB Output is correct
11 Correct 882 ms 80548 KB Output is correct
12 Correct 878 ms 80548 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -