oj.uz

답안 #293155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
293155 2020-09-07T17:00:12 Z _7_7_ 자리 배치 (IOI18_seats) C++14
100 / 100
 3771 ms 52988 KB 
#include "seats.h"
#include <bits/stdc++.h>                                           
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;  
typedef unsigned long long ull;         
typedef vector < pii > vpii;                                   	
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 2e5 + 48, mod = 998244353, N = 1e6 + 12;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 300;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;

int n, m, t[N << 2], tt[N << 2], lz[N << 2], a[N], tmp[4], k;
vi r, c, q;

void build (int v = 1, int tl = 0, int tr = n*m - 1) {
    tt[v] = tr - tl + 1;
	if (tl == tr)
		return;

	int tm = (tl + tr) >> 1;
	build(v << 1, tl, tm);
	build(v << 1 | 1, tm + 1, tr);
}


void update (int l, int r, int x, int v = 1, int tl = 0, int tr = n*m - 1) {
	if (l > r || tl > r || l > tr)
		return;
	if (l <= tl && tr <= r) {
		t[v] += x;
		lz[v] += x;
		return;
	}

	int tm = (tl + tr) >> 1;
	update(l, r, x, v << 1, tl, tm);
	update(l, r, x, v << 1 | 1, tm + 1, tr);
	if (t[v << 1] < t[v << 1 | 1]) {
		t[v] = t[v << 1];
		tt[v] = tt[v << 1];
	} else if (t[v << 1] > t[v << 1 | 1]) {
		t[v] = t[v << 1 | 1];
		tt[v] = tt[v << 1 | 1];	
	} else {
		t[v] = t[v << 1];
		tt[v] = tt[v << 1] + tt[v << 1 | 1];
	}			

	t[v] += lz[v];
}

                                                   
bool in (int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < m;
}

void upd (int x, int y, int z) {
	k = 0;	
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j) {
			int tox = x + i, toy = y + j;
			tmp[k++] = in(tox, toy) ? a[tox*m + toy] : n*m;
		}

	sort(tmp, tmp + 4);
	update(tmp[0], tmp[1] - 1, z);
	update(tmp[2], tmp[3] - 1, z);
}

void give_initial_chart (int _n, int _m, vi _r, vi _c) {
	n = _n;
	m = _m;
	r = _r;
	c = _c;
	
	for (int i = 0; i < n*m; ++i)
		a[r[i]*m + c[i]] = i;

		
	build();
	for (int i = -1; i < n; ++i)
		for (int j = -1; j < m; ++j) 
			upd(i, j, 1);
}       	


int swap_seats(int i, int j) {
	for (int x = -1; x < 1; ++x)
		for (int y = -1; y < 1; ++y) {
			upd(r[i] + x, c[i] + y, -1);
			upd(r[j] + x, c[j] + y, -1);             
		}
	
	swap(r[i], r[j]);
	swap(c[i], c[j]);
	swap(a[r[i]*m + c[i]], a[r[j]*m + c[j]]);	

	for (int x = -1; x < 1; ++x)
		for (int y = -1; y < 1; ++y) {
			upd(r[i] + x, c[i] + y, 1);
			upd(r[j] + x, c[j] + y, 1);             
		}
	return tt[1];
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 512 KB Output is correct
2 Correct 20 ms 488 KB Output is correct
3 Correct 32 ms 460 KB Output is correct
4 Correct 20 ms 512 KB Output is correct
5 Correct 17 ms 512 KB Output is correct
6 Correct 29 ms 504 KB Output is correct
7 Correct 29 ms 504 KB Output is correct
8 Correct 29 ms 504 KB Output is correct
9 Correct 26 ms 504 KB Output is correct
10 Correct 29 ms 512 KB Output is correct
11 Correct 27 ms 512 KB Output is correct
12 Correct 18 ms 512 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 512 KB Output is correct
2 Correct 20 ms 488 KB Output is correct
3 Correct 32 ms 460 KB Output is correct
4 Correct 20 ms 512 KB Output is correct
5 Correct 17 ms 512 KB Output is correct
6 Correct 29 ms 504 KB Output is correct
7 Correct 29 ms 504 KB Output is correct
8 Correct 29 ms 504 KB Output is correct
9 Correct 26 ms 504 KB Output is correct
10 Correct 29 ms 512 KB Output is correct
11 Correct 27 ms 512 KB Output is correct
12 Correct 18 ms 512 KB Output is correct
13 Correct 74 ms 1024 KB Output is correct
14 Correct 86 ms 1024 KB Output is correct
15 Correct 52 ms 1024 KB Output is correct
16 Correct 39 ms 1084 KB Output is correct
17 Correct 62 ms 1024 KB Output is correct
18 Correct 61 ms 1084 KB Output is correct
19 Correct 57 ms 1080 KB Output is correct
20 Correct 49 ms 1024 KB Output is correct
21 Correct 39 ms 1024 KB Output is correct
22 Correct 39 ms 1024 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2463 ms 52476 KB Output is correct
2 Correct 1304 ms 52600 KB Output is correct
3 Correct 1279 ms 52488 KB Output is correct
4 Correct 1103 ms 52472 KB Output is correct
5 Correct 1163 ms 52704 KB Output is correct
6 Correct 1108 ms 52444 KB Output is correct
7 Correct 1192 ms 52392 KB Output is correct
8 Correct 1264 ms 52496 KB Output is correct
9 Correct 1278 ms 52472 KB Output is correct
10 Correct 1232 ms 52524 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 1024 KB Output is correct
2 Correct 180 ms 5984 KB Output is correct
3 Correct 1181 ms 52600 KB Output is correct
4 Correct 2457 ms 52476 KB Output is correct
5 Correct 1101 ms 50680 KB Output is correct
6 Correct 2163 ms 52600 KB Output is correct
7 Correct 1123 ms 52108 KB Output is correct
8 Correct 1351 ms 52600 KB Output is correct
9 Correct 1261 ms 51836 KB Output is correct
10 Correct 1189 ms 52492 KB Output is correct
11 Correct 1138 ms 51696 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 1400 KB Output is correct
2 Correct 109 ms 1396 KB Output is correct
3 Correct 168 ms 1376 KB Output is correct
4 Correct 227 ms 1524 KB Output is correct
5 Correct 386 ms 2036 KB Output is correct
6 Correct 1621 ms 52028 KB Output is correct
7 Correct 1864 ms 52824 KB Output is correct
8 Correct 1596 ms 51056 KB Output is correct
9 Correct 3049 ms 52856 KB Output is correct
10 Correct 1527 ms 52088 KB Output is correct
11 Correct 1548 ms 51960 KB Output is correct
12 Correct 1519 ms 50972 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 512 KB Output is correct
2 Correct 20 ms 488 KB Output is correct
3 Correct 32 ms 460 KB Output is correct
4 Correct 20 ms 512 KB Output is correct
5 Correct 17 ms 512 KB Output is correct
6 Correct 29 ms 504 KB Output is correct
7 Correct 29 ms 504 KB Output is correct
8 Correct 29 ms 504 KB Output is correct
9 Correct 26 ms 504 KB Output is correct
10 Correct 29 ms 512 KB Output is correct
11 Correct 27 ms 512 KB Output is correct
12 Correct 18 ms 512 KB Output is correct
13 Correct 74 ms 1024 KB Output is correct
14 Correct 86 ms 1024 KB Output is correct
15 Correct 52 ms 1024 KB Output is correct
16 Correct 39 ms 1084 KB Output is correct
17 Correct 62 ms 1024 KB Output is correct
18 Correct 61 ms 1084 KB Output is correct
19 Correct 57 ms 1080 KB Output is correct
20 Correct 49 ms 1024 KB Output is correct
21 Correct 39 ms 1024 KB Output is correct
22 Correct 39 ms 1024 KB Output is correct
23 Correct 2463 ms 52476 KB Output is correct
24 Correct 1304 ms 52600 KB Output is correct
25 Correct 1279 ms 52488 KB Output is correct
26 Correct 1103 ms 52472 KB Output is correct
27 Correct 1163 ms 52704 KB Output is correct
28 Correct 1108 ms 52444 KB Output is correct
29 Correct 1192 ms 52392 KB Output is correct
30 Correct 1264 ms 52496 KB Output is correct
31 Correct 1278 ms 52472 KB Output is correct
32 Correct 1232 ms 52524 KB Output is correct
33 Correct 71 ms 1024 KB Output is correct
34 Correct 180 ms 5984 KB Output is correct
35 Correct 1181 ms 52600 KB Output is correct
36 Correct 2457 ms 52476 KB Output is correct
37 Correct 1101 ms 50680 KB Output is correct
38 Correct 2163 ms 52600 KB Output is correct
39 Correct 1123 ms 52108 KB Output is correct
40 Correct 1351 ms 52600 KB Output is correct
41 Correct 1261 ms 51836 KB Output is correct
42 Correct 1189 ms 52492 KB Output is correct
43 Correct 1138 ms 51696 KB Output is correct
44 Correct 83 ms 1400 KB Output is correct
45 Correct 109 ms 1396 KB Output is correct
46 Correct 168 ms 1376 KB Output is correct
47 Correct 227 ms 1524 KB Output is correct
48 Correct 386 ms 2036 KB Output is correct
49 Correct 1621 ms 52028 KB Output is correct
50 Correct 1864 ms 52824 KB Output is correct
51 Correct 1596 ms 51056 KB Output is correct
52 Correct 3049 ms 52856 KB Output is correct
53 Correct 1527 ms 52088 KB Output is correct
54 Correct 1548 ms 51960 KB Output is correct
55 Correct 1519 ms 50972 KB Output is correct
56 Correct 136 ms 1396 KB Output is correct
57 Correct 316 ms 1652 KB Output is correct
58 Correct 543 ms 2164 KB Output is correct
59 Correct 2103 ms 52984 KB Output is correct
60 Correct 3771 ms 52872 KB Output is correct
61 Correct 1956 ms 52728 KB Output is correct
62 Correct 1681 ms 50680 KB Output is correct
63 Correct 3538 ms 52924 KB Output is correct
64 Correct 2266 ms 52988 KB Output is correct
65 Correct 2019 ms 52984 KB Output is correct
66 Correct 2224 ms 51984 KB Output is correct
67 Correct 2196 ms 52756 KB Output is correct
68 Correct 1762 ms 52520 KB Output is correct
69 Correct 3136 ms 52856 KB Output is correct