oj.uz

Submission #218692

# Submission time Handle Problem Language Result Execution time Memory
218692 2020-04-02T14:09:59 Z MarcoMeijer Seats (IOI18_seats) C++14
100 / 100
 3125 ms 105216 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
 
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MX=1e6+1e5;

int h, w, n;
vi r, c;
vector<vi> A;
int dx[]={-1, 0, 1, 0};
int dy[]={ 0,-1, 0, 1};

int SEG[MX*4], SEGMIN[MX*4], SEGCNT[MX*4];
 
inline void updateNode(int p, int lp, int rp) {
	SEG   [p] = 0;
	SEGMIN[p] = min(SEGMIN[lp], SEGMIN[rp]);
	SEGCNT[p] = 0;
	if(SEGMIN[lp] == SEGMIN[p]) SEGCNT[p] += SEGCNT[lp];
	if(SEGMIN[rp] == SEGMIN[p]) SEGCNT[p] += SEGCNT[rp];
}
void buildSeg(int p=0, int L=0, int R=n-1) {
	if(L == R) {
		SEG[p] = 0;
		SEGMIN[p] = 0;
		SEGCNT[p] = 1;
		return;
	}
	int m=(L+R)/2;
	int lp=p*2+1;
	int rp=p*2+2;
	buildSeg(lp,L,m);
	buildSeg(rp,m+1,R);
	updateNode(p,lp,rp);
}
void addSeg(int i, int j, int x, int lazy=0, int p=0, int L=0, int R=n-1) {
	SEG   [p] += lazy;
	SEGMIN[p] += lazy;
	if(j < L || i > R) return;
	if(i <= L && j >= R) {
		SEG   [p] += x; 
		SEGMIN[p] += x; 
		return;
	}
	int m=(L+R)/2;
	int lp=p*2+1;
	int rp=p*2+2;
	addSeg(i,j,x,SEG[p],lp,L,m);
	addSeg(i,j,x,SEG[p],rp,m+1,R);
	updateNode(p,lp,rp);
}
int getEnd(ii pos) {
	if(pos.fi == -1 || pos.fi == h) return n-1;
	if(pos.se == -1 || pos.se == w) return n-1;
	return A[pos.fi][pos.se]-1;
}
void updateNeigbours(ii cent, ii pos1, ii pos2, int x=1) {
	if(getEnd(cent) == n-1) return;
	int bg = A[cent.fi][cent.se];
	int ed = min(getEnd(pos1), getEnd(pos2));
	if(ed >= bg) addSeg(bg, ed, x);
}
void updateNeigbours2(ii cent, ii pos1, ii pos2, int x=1) {
	if(getEnd(cent) == n-1) return;
	int bg = max(getEnd(pos1), getEnd(pos2))+1;
	int ed = A[cent.fi][cent.se]-1;
	if(ed >= bg) addSeg(bg, ed, x);
}
void updateNeigbours(ii cent, int d, int x=1) {
	int d1 = d;
	int d2 = (d+1)%4;
	ii pos1 = {cent.fi+dx[d1], cent.se+dy[d1]};
	ii pos2 = {cent.fi+dx[d2], cent.se+dy[d2]};
	updateNeigbours(cent, pos1, pos2, x);
	if(d == 0) updateNeigbours2(cent, pos1, pos2, x);
}

void give_initial_chart(int H, int W, vi R, vi C) {
	h=H, w=W, r=R, c=C;
	n = h*w;

	A.resize(h);
	RE(i,h) A[i].resize(w);
	RE(i,n) A[r[i]][c[i]] = i;

	buildSeg();
	RE(i,h) RE(j,w) RE(k,4) updateNeigbours({i,j}, k);
}

int swap_seats(int a, int b) {
	set<pair<ii, int>> updated;

	// a's neighbours
	RE(i,4) updated.insert({{r[a],c[a]}, i});
	updated.insert({{r[a]+1,c[a]  }, 0});
	updated.insert({{r[a]-1,c[a]  }, 1});
	updated.insert({{r[a]-1,c[a]  }, 2});
	updated.insert({{r[a]+1,c[a]  }, 3});
	updated.insert({{r[a]  ,c[a]+1}, 0});
	updated.insert({{r[a]  ,c[a]+1}, 1});
	updated.insert({{r[a]  ,c[a]-1}, 2});
	updated.insert({{r[a]  ,c[a]-1}, 3});

	// b's neighbours
	RE(i,4) updated.insert({{r[b],c[b]}, i});
	updated.insert({{r[b]+1,c[b]  }, 0});
	updated.insert({{r[b]-1,c[b]  }, 1});
	updated.insert({{r[b]-1,c[b]  }, 2});
	updated.insert({{r[b]+1,c[b]  }, 3});
	updated.insert({{r[b]  ,c[b]+1}, 0});
	updated.insert({{r[b]  ,c[b]+1}, 1});
	updated.insert({{r[b]  ,c[b]-1}, 2});
	updated.insert({{r[b]  ,c[b]-1}, 3});

	for(auto p : updated) updateNeigbours(p.fi, p.se, -1);

	swap(r[a], r[b]);
	swap(c[a], c[b]);
	A[r[a]][c[a]] = a;
	A[r[b]][c[b]] = b;

	for(auto p : updated) updateNeigbours(p.fi, p.se, 1);

	if(SEGMIN[0] != 4) return 0;
	else return SEGCNT[0]; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 512 KB Output is correct
2 Correct 35 ms 512 KB Output is correct
3 Correct 46 ms 512 KB Output is correct
4 Correct 38 ms 512 KB Output is correct
5 Correct 35 ms 512 KB Output is correct
6 Correct 43 ms 512 KB Output is correct
7 Correct 44 ms 512 KB Output is correct
8 Correct 41 ms 512 KB Output is correct
9 Correct 42 ms 512 KB Output is correct
10 Correct 43 ms 512 KB Output is correct
11 Correct 43 ms 512 KB Output is correct
12 Correct 35 ms 512 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 512 KB Output is correct
2 Correct 35 ms 512 KB Output is correct
3 Correct 46 ms 512 KB Output is correct
4 Correct 38 ms 512 KB Output is correct
5 Correct 35 ms 512 KB Output is correct
6 Correct 43 ms 512 KB Output is correct
7 Correct 44 ms 512 KB Output is correct
8 Correct 41 ms 512 KB Output is correct
9 Correct 42 ms 512 KB Output is correct
10 Correct 43 ms 512 KB Output is correct
11 Correct 43 ms 512 KB Output is correct
12 Correct 35 ms 512 KB Output is correct
13 Correct 80 ms 1272 KB Output is correct
14 Correct 84 ms 1272 KB Output is correct
15 Correct 77 ms 1272 KB Output is correct
16 Correct 58 ms 1784 KB Output is correct
17 Correct 74 ms 1272 KB Output is correct
18 Correct 67 ms 1272 KB Output is correct
19 Correct 66 ms 1400 KB Output is correct
20 Correct 59 ms 1536 KB Output is correct
21 Correct 58 ms 1276 KB Output is correct
22 Correct 61 ms 1792 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2119 ms 55672 KB Output is correct
2 Correct 1044 ms 56312 KB Output is correct
3 Correct 1084 ms 56184 KB Output is correct
4 Correct 1016 ms 56184 KB Output is correct
5 Correct 1206 ms 56068 KB Output is correct
6 Correct 895 ms 56184 KB Output is correct
7 Correct 956 ms 56184 KB Output is correct
8 Correct 982 ms 56196 KB Output is correct
9 Correct 971 ms 56184 KB Output is correct
10 Correct 1053 ms 56200 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 1272 KB Output is correct
2 Correct 185 ms 7032 KB Output is correct
3 Correct 954 ms 55920 KB Output is correct
4 Correct 2156 ms 55692 KB Output is correct
5 Correct 1195 ms 54648 KB Output is correct
6 Correct 2404 ms 105216 KB Output is correct
7 Correct 1056 ms 54312 KB Output is correct
8 Correct 1033 ms 54264 KB Output is correct
9 Correct 1016 ms 54776 KB Output is correct
10 Correct 1157 ms 57464 KB Output is correct
11 Correct 1137 ms 77816 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 2036 KB Output is correct
2 Correct 237 ms 2164 KB Output is correct
3 Correct 304 ms 2036 KB Output is correct
4 Correct 391 ms 2292 KB Output is correct
5 Correct 546 ms 2804 KB Output is correct
6 Correct 1783 ms 54776 KB Output is correct
7 Correct 2095 ms 54832 KB Output is correct
8 Correct 1771 ms 54832 KB Output is correct
9 Correct 2979 ms 54804 KB Output is correct
10 Correct 1725 ms 54688 KB Output is correct
11 Correct 1731 ms 54904 KB Output is correct
12 Correct 1652 ms 55032 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 512 KB Output is correct
2 Correct 35 ms 512 KB Output is correct
3 Correct 46 ms 512 KB Output is correct
4 Correct 38 ms 512 KB Output is correct
5 Correct 35 ms 512 KB Output is correct
6 Correct 43 ms 512 KB Output is correct
7 Correct 44 ms 512 KB Output is correct
8 Correct 41 ms 512 KB Output is correct
9 Correct 42 ms 512 KB Output is correct
10 Correct 43 ms 512 KB Output is correct
11 Correct 43 ms 512 KB Output is correct
12 Correct 35 ms 512 KB Output is correct
13 Correct 80 ms 1272 KB Output is correct
14 Correct 84 ms 1272 KB Output is correct
15 Correct 77 ms 1272 KB Output is correct
16 Correct 58 ms 1784 KB Output is correct
17 Correct 74 ms 1272 KB Output is correct
18 Correct 67 ms 1272 KB Output is correct
19 Correct 66 ms 1400 KB Output is correct
20 Correct 59 ms 1536 KB Output is correct
21 Correct 58 ms 1276 KB Output is correct
22 Correct 61 ms 1792 KB Output is correct
23 Correct 2119 ms 55672 KB Output is correct
24 Correct 1044 ms 56312 KB Output is correct
25 Correct 1084 ms 56184 KB Output is correct
26 Correct 1016 ms 56184 KB Output is correct
27 Correct 1206 ms 56068 KB Output is correct
28 Correct 895 ms 56184 KB Output is correct
29 Correct 956 ms 56184 KB Output is correct
30 Correct 982 ms 56196 KB Output is correct
31 Correct 971 ms 56184 KB Output is correct
32 Correct 1053 ms 56200 KB Output is correct
33 Correct 86 ms 1272 KB Output is correct
34 Correct 185 ms 7032 KB Output is correct
35 Correct 954 ms 55920 KB Output is correct
36 Correct 2156 ms 55692 KB Output is correct
37 Correct 1195 ms 54648 KB Output is correct
38 Correct 2404 ms 105216 KB Output is correct
39 Correct 1056 ms 54312 KB Output is correct
40 Correct 1033 ms 54264 KB Output is correct
41 Correct 1016 ms 54776 KB Output is correct
42 Correct 1157 ms 57464 KB Output is correct
43 Correct 1137 ms 77816 KB Output is correct
44 Correct 166 ms 2036 KB Output is correct
45 Correct 237 ms 2164 KB Output is correct
46 Correct 304 ms 2036 KB Output is correct
47 Correct 391 ms 2292 KB Output is correct
48 Correct 546 ms 2804 KB Output is correct
49 Correct 1783 ms 54776 KB Output is correct
50 Correct 2095 ms 54832 KB Output is correct
51 Correct 1771 ms 54832 KB Output is correct
52 Correct 2979 ms 54804 KB Output is correct
53 Correct 1725 ms 54688 KB Output is correct
54 Correct 1731 ms 54904 KB Output is correct
55 Correct 1652 ms 55032 KB Output is correct
56 Correct 274 ms 2164 KB Output is correct
57 Correct 411 ms 2036 KB Output is correct
58 Correct 549 ms 2804 KB Output is correct
59 Correct 1592 ms 54724 KB Output is correct
60 Correct 3109 ms 52984 KB Output is correct
61 Correct 1743 ms 69512 KB Output is correct
62 Correct 1585 ms 69392 KB Output is correct
63 Correct 3053 ms 69432 KB Output is correct
64 Correct 1989 ms 69372 KB Output is correct
65 Correct 1609 ms 69624 KB Output is correct
66 Correct 1694 ms 69884 KB Output is correct
67 Correct 1939 ms 72568 KB Output is correct
68 Correct 1726 ms 83960 KB Output is correct
69 Correct 3125 ms 93176 KB Output is correct