oj.uz

Submission #421548

# Submission time Handle Problem Language Result Execution time Memory
421548 2021-06-09T08:55:16 Z amoo_safar Seats (IOI18_seats) C++17
100 / 100
 3111 ms 122056 KB 
#include "seats.h"

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

typedef pair<int, int> pii;

const int N = 1e6 + 10;

vector< vector<int> > gr;

int fl;
int ps[N];

struct Segment {
	pii seg[N << 2];
	int lz[N << 2];
	int sz;
	void Apply(int id, int x){
		seg[id].F += x;
		lz[id] += x;
	}
	void Shift(int id){
		Apply(id << 1, lz[id]);
		Apply(id<<1|1, lz[id]);
		lz[id] = 0;
	}
	pii Merge(pii A, pii B){
		int mn = min(A.F, B.F);
		int cnt = 0;
		if(mn == A.F) cnt += A.S;
		if(mn == B.F) cnt += B.S;
		return {mn, cnt};
	}
	void Build(int id, int L, int R){
		lz[id] = 0;
		if(L + 1 == R){
			seg[id] = {ps[L], 1};
			return ;
		}
		int mid = (L + R) >> 1;
		Build(id << 1, L, mid);
		Build(id<<1|1, mid, R);
		seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
	}
	void Build(int _sz){
		sz = _sz;
		fl = 1;
		for(int i = 1; i < N; i++)
			ps[i] += ps[i - 1];
		Build(1, 0, sz);
	}

	void Add(int l, int r, int x, int id = 1, int L = 0, int R = 0){
		if(id == 1){
			if(!fl){
				ps[l] += x;
				ps[r] -= x;
				return;
			}
			R = sz;
		}
		if(r <= L || R <= l) return ;
		if(l <= L && R <= r){
			Apply(id, x);
			return;
		}
		Shift(id);
		int mid = (L + R) >> 1;
		Add(l, r, x, id << 1, L, mid);
		Add(l, r, x, id<<1|1, mid, R);
		seg[id] = Merge(seg[id<<1], seg[id << 1 | 1]);
	}
	pii Get(){
		return seg[1];
		// int mn = *min_element(seg, seg + sz);
		// int cnt = 0;
		// for(int i = 0; i < sz; i++)
		// 	cnt += (seg[i] == mn);
		// return {mn, cnt};
	}
};
Segment DS;

void Add(int x, int y, int z){
	vector<pii> V = {{x, y}, {x, y + 1}, {x + 1, y}, {x + 1, y + 1}};
	sort(V.begin(), V.end(), [&](auto A, auto B){ return gr[A.F][A.S] < gr[B.F][B.S]; });
	vector<int> vl;
	for(auto [i, j] : V) vl.push_back(gr[i][j]);
	DS.Add(vl[0], vl[1], z * (+1));
	DS.Add(vl[2], vl[3], z * (+1));
	if(V[0].F != V[1].F && V[0].S != V[1].S)
		DS.Add(vl[1], vl[2], z * (+1));
}
vector<int> pR, pC;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	pR = R; pC = C;
	// r = R;
	gr.resize(H + 2, vector<int>(W + 2, H*W));
	for(int i = 0; i < H*W; i++)
		gr[R[i] + 1][C[i] + 1] = i;
	for(int i = 0; i <= H; i++)
		for(int j = 0; j <= W; j++)
			Add(i, j, 1);
	DS.Build(H*W);
}

void Change(int x, int y, int w){
	Add(x, y, -1);
	Add(x - 1, y, -1);
	Add(x, y - 1, -1);
	Add(x-1, y-1, -1);
	gr[x][y] = w;
	Add(x, y, +1);
	Add(x - 1, y, +1);
	Add(x, y - 1, +1);
	Add(x-1, y-1, +1);
}

int swap_seats(int a, int b) {
	Change(pR[a] + 1, pC[a] + 1, b);
	swap(a, b);
	Change(pR[a] + 1, pC[a] + 1, b);
	swap(pR[a], pR[b]);
	swap(pC[a], pC[b]);

	pii res = DS.Get();
	return res.F <= 4 ? res.S : 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 35624 KB Output is correct
2 Correct 56 ms 35560 KB Output is correct
3 Correct 82 ms 35572 KB Output is correct
4 Correct 50 ms 35516 KB Output is correct
5 Correct 51 ms 35584 KB Output is correct
6 Correct 63 ms 35584 KB Output is correct
7 Correct 75 ms 35580 KB Output is correct
8 Correct 82 ms 35604 KB Output is correct
9 Correct 69 ms 35632 KB Output is correct
10 Correct 73 ms 35580 KB Output is correct
11 Correct 61 ms 35588 KB Output is correct
12 Correct 47 ms 35576 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 35624 KB Output is correct
2 Correct 56 ms 35560 KB Output is correct
3 Correct 82 ms 35572 KB Output is correct
4 Correct 50 ms 35516 KB Output is correct
5 Correct 51 ms 35584 KB Output is correct
6 Correct 63 ms 35584 KB Output is correct
7 Correct 75 ms 35580 KB Output is correct
8 Correct 82 ms 35604 KB Output is correct
9 Correct 69 ms 35632 KB Output is correct
10 Correct 73 ms 35580 KB Output is correct
11 Correct 61 ms 35588 KB Output is correct
12 Correct 47 ms 35576 KB Output is correct
13 Correct 164 ms 35952 KB Output is correct
14 Correct 151 ms 35948 KB Output is correct
15 Correct 82 ms 36000 KB Output is correct
16 Correct 71 ms 36420 KB Output is correct
17 Correct 106 ms 36008 KB Output is correct
18 Correct 123 ms 35964 KB Output is correct
19 Correct 97 ms 35996 KB Output is correct
20 Correct 84 ms 36184 KB Output is correct
21 Correct 81 ms 36060 KB Output is correct
22 Correct 77 ms 36464 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 877 ms 71176 KB Output is correct
2 Correct 659 ms 71136 KB Output is correct
3 Correct 659 ms 71204 KB Output is correct
4 Correct 703 ms 71180 KB Output is correct
5 Correct 688 ms 71184 KB Output is correct
6 Correct 649 ms 71216 KB Output is correct
7 Correct 628 ms 71204 KB Output is correct
8 Correct 647 ms 71204 KB Output is correct
9 Correct 627 ms 71192 KB Output is correct
10 Correct 622 ms 71208 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 36080 KB Output is correct
2 Correct 180 ms 38976 KB Output is correct
3 Correct 743 ms 71208 KB Output is correct
4 Correct 802 ms 71240 KB Output is correct
5 Correct 721 ms 79044 KB Output is correct
6 Correct 1029 ms 122056 KB Output is correct
7 Correct 671 ms 73772 KB Output is correct
8 Correct 779 ms 71188 KB Output is correct
9 Correct 724 ms 71568 KB Output is correct
10 Correct 752 ms 75860 KB Output is correct
11 Correct 828 ms 94624 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 36504 KB Output is correct
2 Correct 247 ms 36448 KB Output is correct
3 Correct 335 ms 36488 KB Output is correct
4 Correct 420 ms 36620 KB Output is correct
5 Correct 624 ms 37028 KB Output is correct
6 Correct 1595 ms 79356 KB Output is correct
7 Correct 1626 ms 79344 KB Output is correct
8 Correct 1454 ms 79228 KB Output is correct
9 Correct 1739 ms 79428 KB Output is correct
10 Correct 1388 ms 80864 KB Output is correct
11 Correct 1397 ms 95948 KB Output is correct
12 Correct 1486 ms 95904 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 35624 KB Output is correct
2 Correct 56 ms 35560 KB Output is correct
3 Correct 82 ms 35572 KB Output is correct
4 Correct 50 ms 35516 KB Output is correct
5 Correct 51 ms 35584 KB Output is correct
6 Correct 63 ms 35584 KB Output is correct
7 Correct 75 ms 35580 KB Output is correct
8 Correct 82 ms 35604 KB Output is correct
9 Correct 69 ms 35632 KB Output is correct
10 Correct 73 ms 35580 KB Output is correct
11 Correct 61 ms 35588 KB Output is correct
12 Correct 47 ms 35576 KB Output is correct
13 Correct 164 ms 35952 KB Output is correct
14 Correct 151 ms 35948 KB Output is correct
15 Correct 82 ms 36000 KB Output is correct
16 Correct 71 ms 36420 KB Output is correct
17 Correct 106 ms 36008 KB Output is correct
18 Correct 123 ms 35964 KB Output is correct
19 Correct 97 ms 35996 KB Output is correct
20 Correct 84 ms 36184 KB Output is correct
21 Correct 81 ms 36060 KB Output is correct
22 Correct 77 ms 36464 KB Output is correct
23 Correct 877 ms 71176 KB Output is correct
24 Correct 659 ms 71136 KB Output is correct
25 Correct 659 ms 71204 KB Output is correct
26 Correct 703 ms 71180 KB Output is correct
27 Correct 688 ms 71184 KB Output is correct
28 Correct 649 ms 71216 KB Output is correct
29 Correct 628 ms 71204 KB Output is correct
30 Correct 647 ms 71204 KB Output is correct
31 Correct 627 ms 71192 KB Output is correct
32 Correct 622 ms 71208 KB Output is correct
33 Correct 120 ms 36080 KB Output is correct
34 Correct 180 ms 38976 KB Output is correct
35 Correct 743 ms 71208 KB Output is correct
36 Correct 802 ms 71240 KB Output is correct
37 Correct 721 ms 79044 KB Output is correct
38 Correct 1029 ms 122056 KB Output is correct
39 Correct 671 ms 73772 KB Output is correct
40 Correct 779 ms 71188 KB Output is correct
41 Correct 724 ms 71568 KB Output is correct
42 Correct 752 ms 75860 KB Output is correct
43 Correct 828 ms 94624 KB Output is correct
44 Correct 219 ms 36504 KB Output is correct
45 Correct 247 ms 36448 KB Output is correct
46 Correct 335 ms 36488 KB Output is correct
47 Correct 420 ms 36620 KB Output is correct
48 Correct 624 ms 37028 KB Output is correct
49 Correct 1595 ms 79356 KB Output is correct
50 Correct 1626 ms 79344 KB Output is correct
51 Correct 1454 ms 79228 KB Output is correct
52 Correct 1739 ms 79428 KB Output is correct
53 Correct 1388 ms 80864 KB Output is correct
54 Correct 1397 ms 95948 KB Output is correct
55 Correct 1486 ms 95904 KB Output is correct
56 Correct 284 ms 37164 KB Output is correct
57 Correct 541 ms 37228 KB Output is correct
58 Correct 846 ms 37588 KB Output is correct
59 Correct 2126 ms 88096 KB Output is correct
60 Correct 3111 ms 88160 KB Output is correct
61 Correct 1830 ms 88068 KB Output is correct
62 Correct 1721 ms 92056 KB Output is correct
63 Correct 2718 ms 90724 KB Output is correct
64 Correct 2045 ms 88852 KB Output is correct
65 Correct 1861 ms 88232 KB Output is correct
66 Correct 2152 ms 88472 KB Output is correct
67 Correct 2076 ms 92808 KB Output is correct
68 Correct 1813 ms 102476 KB Output is correct
69 Correct 2657 ms 111488 KB Output is correct