oj.uz

Submission #596995

# Submission time Handle Problem Language Result Execution time Memory
596995 2022-07-15T11:16:36 Z Lucpp Seats (IOI18_seats) C++17
100 / 100
 1364 ms 111032 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

struct Seg{
	vector<pair<int, int>> seg;
	vector<int> lazy;
	int cap;
	pair<int, int> combine(pair<int, int> a, pair<int, int> b){
		if(a > b) swap(a, b);
		if(a.first == b.first) a.second += b.second;
		return a;
	}
	void init(vector<int> v){
		int n = (int)v.size();
		for(int i = 1; i < n; i++) v[i] += v[i-1];
		for(cap = 1; cap < n; cap*=2);
		seg.resize(2*cap, {INF, 1});
		lazy.resize(2*cap, 0);
		for(int i = 0; i < n; i++) seg[i+cap].first = v[i];
		for(int i = cap-1; i >= 1; i--) seg[i] = combine(seg[2*i], seg[2*i+1]);
	}
	void apply(int v, int i){
		seg[i].first += v;
		lazy[i] += v;
	}
	void push(int i){
		apply(lazy[i], 2*i);
		apply(lazy[i], 2*i+1);
		lazy[i] = 0;
	}
	void upd(int l, int r, int v, int a, int b, int i){
		if(l <= a && b <= r) apply(v, i);
		else if(b < l || r < a) return;
		else{
			push(i);
			int m = (a+b)/2;
			upd(l, r, v, a, m, 2*i);
			upd(l, r, v, m+1, b, 2*i+1);
			seg[i] = combine(seg[2*i], seg[2*i+1]);
		}
	}
	void upd(int l, int r, int v){upd(l, r, v, 1, cap, 1);}
};

int n, W, H;
vector<int> r, c;

vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
vector<vector<int>> num;
vector<int> adj;
Seg seg;

int calc(int x, int y){
	int res = 0;
	for(int i = -1; i < 1; i++){
		for(int j = -1; j < 1; j++){
			int cnt = 0;
			for(int a = 0; a < 2; a++){
				for(int b = 0; b < 2; b++){
					int nx = x+i+a;
					int ny = y+j+b;
					if(num[nx][ny] <= num[x][y]) cnt++;
				}
			}
			if(cnt == 1) res++;
			if(cnt == 2) res--;
			if(cnt == 3) res++;
			if(cnt == 4) res--;
		}
	}
	return res;
}

void upd(int x, int y){
	if(x == 0 || x == H+1 || y == 0 || y == W+1) return;
	int res = calc(x, y);
	seg.upd(num[x][y]+1, n+1, res-adj[num[x][y]]);
	adj[num[x][y]] = res;
}

void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
	H = h, W = w;
	n = H*W;
	r = R;
	c = C;
	num.assign(H+2, vector<int>(W+2, INF));
	adj.resize(n);
	for(int i = 0; i < n; i++) num[r[i]+1][c[i]+1] = i;
	for(int i = 0; i < n; i++){
		int x = r[i]+1, y = c[i]+1;
		adj[i] = calc(x, y);
	}
	seg.init(adj);
}

int qry = 0;

int swap_seats(int a, int b) {
	qry++;
	if(a > b) swap(a, b);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	swap(num[r[a]+1][c[a]+1], num[r[b]+1][c[b]+1]);
	for(int i = -1; i <= 1; i++){
		for(int j = -1; j <= 1; j++){
			upd(r[a]+1+i, c[a]+1+j);
			upd(r[b]+1+i, c[b]+1+j);
		}
	}
	int ans = seg.seg[1].second;
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 20 ms 348 KB Output is correct
3 Correct 25 ms 372 KB Output is correct
4 Correct 10 ms 352 KB Output is correct
5 Correct 9 ms 360 KB Output is correct
6 Correct 20 ms 356 KB Output is correct
7 Correct 20 ms 372 KB Output is correct
8 Correct 24 ms 340 KB Output is correct
9 Correct 23 ms 352 KB Output is correct
10 Correct 24 ms 372 KB Output is correct
11 Correct 20 ms 364 KB Output is correct
12 Correct 9 ms 396 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 20 ms 348 KB Output is correct
3 Correct 25 ms 372 KB Output is correct
4 Correct 10 ms 352 KB Output is correct
5 Correct 9 ms 360 KB Output is correct
6 Correct 20 ms 356 KB Output is correct
7 Correct 20 ms 372 KB Output is correct
8 Correct 24 ms 340 KB Output is correct
9 Correct 23 ms 352 KB Output is correct
10 Correct 24 ms 372 KB Output is correct
11 Correct 20 ms 364 KB Output is correct
12 Correct 9 ms 396 KB Output is correct
13 Correct 53 ms 1100 KB Output is correct
14 Correct 56 ms 1088 KB Output is correct
15 Correct 19 ms 1108 KB Output is correct
16 Correct 21 ms 1600 KB Output is correct
17 Correct 38 ms 1156 KB Output is correct
18 Correct 50 ms 1092 KB Output is correct
19 Correct 53 ms 1112 KB Output is correct
20 Correct 34 ms 1320 KB Output is correct
21 Correct 19 ms 1116 KB Output is correct
22 Correct 20 ms 1528 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 60200 KB Output is correct
2 Correct 343 ms 60216 KB Output is correct
3 Correct 350 ms 60212 KB Output is correct
4 Correct 371 ms 60132 KB Output is correct
5 Correct 374 ms 60244 KB Output is correct
6 Correct 343 ms 60236 KB Output is correct
7 Correct 328 ms 60244 KB Output is correct
8 Correct 353 ms 60208 KB Output is correct
9 Correct 333 ms 60132 KB Output is correct
10 Correct 361 ms 60228 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1076 KB Output is correct
2 Correct 93 ms 6516 KB Output is correct
3 Correct 348 ms 60136 KB Output is correct
4 Correct 398 ms 60216 KB Output is correct
5 Correct 294 ms 67944 KB Output is correct
6 Correct 659 ms 111032 KB Output is correct
7 Correct 369 ms 62772 KB Output is correct
8 Correct 329 ms 60228 KB Output is correct
9 Correct 379 ms 60484 KB Output is correct
10 Correct 337 ms 64828 KB Output is correct
11 Correct 338 ms 83660 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1256 KB Output is correct
2 Correct 59 ms 1296 KB Output is correct
3 Correct 93 ms 1356 KB Output is correct
4 Correct 146 ms 1296 KB Output is correct
5 Correct 181 ms 2028 KB Output is correct
6 Correct 604 ms 68312 KB Output is correct
7 Correct 584 ms 68384 KB Output is correct
8 Correct 579 ms 68344 KB Output is correct
9 Correct 689 ms 68332 KB Output is correct
10 Correct 547 ms 68356 KB Output is correct
11 Correct 556 ms 68336 KB Output is correct
12 Correct 543 ms 68348 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 20 ms 348 KB Output is correct
3 Correct 25 ms 372 KB Output is correct
4 Correct 10 ms 352 KB Output is correct
5 Correct 9 ms 360 KB Output is correct
6 Correct 20 ms 356 KB Output is correct
7 Correct 20 ms 372 KB Output is correct
8 Correct 24 ms 340 KB Output is correct
9 Correct 23 ms 352 KB Output is correct
10 Correct 24 ms 372 KB Output is correct
11 Correct 20 ms 364 KB Output is correct
12 Correct 9 ms 396 KB Output is correct
13 Correct 53 ms 1100 KB Output is correct
14 Correct 56 ms 1088 KB Output is correct
15 Correct 19 ms 1108 KB Output is correct
16 Correct 21 ms 1600 KB Output is correct
17 Correct 38 ms 1156 KB Output is correct
18 Correct 50 ms 1092 KB Output is correct
19 Correct 53 ms 1112 KB Output is correct
20 Correct 34 ms 1320 KB Output is correct
21 Correct 19 ms 1116 KB Output is correct
22 Correct 20 ms 1528 KB Output is correct
23 Correct 408 ms 60200 KB Output is correct
24 Correct 343 ms 60216 KB Output is correct
25 Correct 350 ms 60212 KB Output is correct
26 Correct 371 ms 60132 KB Output is correct
27 Correct 374 ms 60244 KB Output is correct
28 Correct 343 ms 60236 KB Output is correct
29 Correct 328 ms 60244 KB Output is correct
30 Correct 353 ms 60208 KB Output is correct
31 Correct 333 ms 60132 KB Output is correct
32 Correct 361 ms 60228 KB Output is correct
33 Correct 53 ms 1076 KB Output is correct
34 Correct 93 ms 6516 KB Output is correct
35 Correct 348 ms 60136 KB Output is correct
36 Correct 398 ms 60216 KB Output is correct
37 Correct 294 ms 67944 KB Output is correct
38 Correct 659 ms 111032 KB Output is correct
39 Correct 369 ms 62772 KB Output is correct
40 Correct 329 ms 60228 KB Output is correct
41 Correct 379 ms 60484 KB Output is correct
42 Correct 337 ms 64828 KB Output is correct
43 Correct 338 ms 83660 KB Output is correct
44 Correct 30 ms 1256 KB Output is correct
45 Correct 59 ms 1296 KB Output is correct
46 Correct 93 ms 1356 KB Output is correct
47 Correct 146 ms 1296 KB Output is correct
48 Correct 181 ms 2028 KB Output is correct
49 Correct 604 ms 68312 KB Output is correct
50 Correct 584 ms 68384 KB Output is correct
51 Correct 579 ms 68344 KB Output is correct
52 Correct 689 ms 68332 KB Output is correct
53 Correct 547 ms 68356 KB Output is correct
54 Correct 556 ms 68336 KB Output is correct
55 Correct 543 ms 68348 KB Output is correct
56 Correct 105 ms 1332 KB Output is correct
57 Correct 248 ms 1248 KB Output is correct
58 Correct 549 ms 2012 KB Output is correct
59 Correct 1169 ms 60600 KB Output is correct
60 Correct 1364 ms 60604 KB Output is correct
61 Correct 977 ms 60492 KB Output is correct
62 Correct 771 ms 64532 KB Output is correct
63 Correct 1010 ms 79668 KB Output is correct
64 Correct 1067 ms 77940 KB Output is correct
65 Correct 1034 ms 77232 KB Output is correct
66 Correct 1100 ms 77492 KB Output is correct
67 Correct 1004 ms 81808 KB Output is correct
68 Correct 773 ms 91460 KB Output is correct
69 Correct 1196 ms 100556 KB Output is correct