oj.uz

답안 #103341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103341 2019-03-29T18:56:46 Z aviroop123 자리 배치 (IOI18_seats) C++14
100 / 100
 2645 ms 184568 KB 
#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
// using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
// #define int long long 
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
const int mod = 1e9 + 7;
const int mod1 = 998244353;
typedef long double f80;
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#define endl '\n'
#endif
 
// template<typename T>
// using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
ll pwr(ll a,ll b){
	a %= mod;
    int ans = 1;
    while(b){
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
const int N = 1e6 + 5;
pair<int,int> tr[2 * N][2];
int tot;
int d[2 * N];
pii pos[N];
int n, h;
void build1(){
	n = tot + 1;
	h = sizeof(int) * 8 - __builtin_clz(n);
	fr(i, n, 2 * n - 1){
		tr[i][0].fi = 0, tr[i][0].se = 1;
		tr[i][1].fi = 1e9, tr[i][1].se = 0;
	}
	for(int i = n - 1; i > 0; i--){
		tr[i][0].fi = 0, tr[i][0].se = tr[i << 1][0].se + tr[i << 1 | 1][0].se;
		tr[i][1].fi = 1e9, tr[i][1].se = 0;
	}
}
vector<vector<int>> m;
vector<vector<bool>> active;
int dx[4] = {0, 0, -1, -1};
int dy[4] = {0, -1, 0, -1};
int pp[4] = {1, 2, 2, 1};
void apply(int p, int value){
	tr[p][0].fi += value;
	tr[p][1].fi += value;
	if(p < n) d[p] += value;
}
void push(int p){
	for(int s = h; s > 0; --s){
	    int i = p >> s;
	    if (d[i] != 0){
	      	apply(i << 1, d[i]);
	      	apply(i << 1 | 1, d[i]);
	      	d[i] = 0;
	    }
	}
}
void build(int nd) {
  	while(nd > 1){
	  	nd >>= 1;
	  	int pt1 = 0, pt2 = 0, pt = 0;
		int nd1 = nd << 1, nd2 = nd1 | 1;
		while(pt1 < 2 && pt2 < 2 && pt < 2){
			if(tr[nd1][pt1].fi < tr[nd2][pt2].fi){
				tr[nd][pt++] = tr[nd1][pt1++];
			}
			else if(tr[nd1][pt1].fi > tr[nd2][pt2].fi){
				tr[nd][pt++] = tr[nd2][pt2++];
			}
			else{
				tr[nd][pt++] = {tr[nd1][pt1].fi, tr[nd1][pt1].se + tr[nd2][pt2].se};
				pt1++, pt2++;
			}
		}
		tr[nd][0].fi += d[nd];
		tr[nd][1].fi += d[nd];
  	}
}
void inc(int l, int r, int value){
	r++;
	l += n, r += n;
	int l0 = l, r0 = r;
	for(;l < r; l >>= 1, r >>= 1){
		if(l & 1) apply(l++, value);
		if(r & 1) apply(--r, value);
	}
	build(l0);
	build(r0 - 1);
}
vector<pii> lol;
void add_box(int x,int y,int val){
	if(!active[x][y] && val == -1) return;
	if(active[x][y] && val == 1) return;
	active[x][y] = !active[x][y];
	x++, y++;
	fr(i, 0, 3)
		lol.pb({m[x + dx[i]][y + dy[i]], pp[i]});
	sort(all(lol));
	if(lol[0].fi <= tot && lol[0].fi == m[x][y])
		inc(lol[0].fi, min(lol[1].fi - 1, tot), val);
	if(lol[0].se == lol[1].se && lol[1].fi <= tot)
		inc(lol[1].fi, min(lol[3].fi - 1, tot), 2 * val);
	else if(lol[2].fi <= tot)
		inc(lol[2].fi, min(lol[3].fi - 1, tot), 2 * val);
	lol.clear();
}
void give_initial_chart(int h,int w,vector<int> r,vector<int> c){
	tot = h * w - 1;
	build1();
	m.resize(h + 2);
	active.resize(h + 2);
	fr(i, 0, h + 1){
		m[i].resize(w + 2, 1e9);
		active[i].resize(w + 2, 0);
	}
	fr(i, 0, tot){
		pos[i] = {r[i] + 1, c[i] + 1};
		m[r[i] + 1][c[i] + 1] = i;
	}
	for(int i = 0; i <= h; i++){
		for(int j = 0; j <= w; j++){
			add_box(i, j, 1);
		}
	}
}
int swap_seats(int a,int b){
	fr(i, 0, 3){
		add_box(pos[a].fi + dx[i], pos[a].se + dy[i], -1);
		add_box(pos[b].fi + dx[i], pos[b].se + dy[i], -1);
	}
	swap(pos[a], pos[b]);
	m[pos[a].fi][pos[a].se] = a;
	m[pos[b].fi][pos[b].se] = b;
	fr(i, 0, 3){
		add_box(pos[a].fi + dx[i], pos[a].se + dy[i], 1);
		add_box(pos[b].fi + dx[i], pos[b].se + dy[i], 1);
	}
	int ans = 0;
	fr(i, 0, 1){
		if(tr[1][i].fi == 1){
			ans = tr[1][i].se;
			break;
		}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 512 KB Output is correct
2 Correct 18 ms 512 KB Output is correct
3 Correct 22 ms 504 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 9 ms 512 KB Output is correct
6 Correct 18 ms 504 KB Output is correct
7 Correct 20 ms 504 KB Output is correct
8 Correct 21 ms 512 KB Output is correct
9 Correct 21 ms 504 KB Output is correct
10 Correct 21 ms 512 KB Output is correct
11 Correct 21 ms 512 KB Output is correct
12 Correct 11 ms 512 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 512 KB Output is correct
2 Correct 18 ms 512 KB Output is correct
3 Correct 22 ms 504 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 9 ms 512 KB Output is correct
6 Correct 18 ms 504 KB Output is correct
7 Correct 20 ms 504 KB Output is correct
8 Correct 21 ms 512 KB Output is correct
9 Correct 21 ms 504 KB Output is correct
10 Correct 21 ms 512 KB Output is correct
11 Correct 21 ms 512 KB Output is correct
12 Correct 11 ms 512 KB Output is correct
13 Correct 43 ms 1024 KB Output is correct
14 Correct 52 ms 1024 KB Output is correct
15 Correct 23 ms 1152 KB Output is correct
16 Correct 19 ms 2304 KB Output is correct
17 Correct 35 ms 1144 KB Output is correct
18 Correct 45 ms 1088 KB Output is correct
19 Correct 37 ms 1152 KB Output is correct
20 Correct 39 ms 1656 KB Output is correct
21 Correct 30 ms 1144 KB Output is correct
22 Correct 25 ms 2296 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1628 ms 63352 KB Output is correct
2 Correct 945 ms 63356 KB Output is correct
3 Correct 972 ms 63352 KB Output is correct
4 Correct 688 ms 59920 KB Output is correct
5 Correct 675 ms 63456 KB Output is correct
6 Correct 1059 ms 63352 KB Output is correct
7 Correct 923 ms 63224 KB Output is correct
8 Correct 749 ms 60408 KB Output is correct
9 Correct 982 ms 59512 KB Output is correct
10 Correct 968 ms 61432 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 1024 KB Output is correct
2 Correct 132 ms 6008 KB Output is correct
3 Correct 762 ms 63324 KB Output is correct
4 Correct 1573 ms 63328 KB Output is correct
5 Correct 767 ms 67448 KB Output is correct
6 Correct 1556 ms 184568 KB Output is correct
7 Correct 667 ms 63964 KB Output is correct
8 Correct 1218 ms 63224 KB Output is correct
9 Correct 803 ms 60792 KB Output is correct
10 Correct 921 ms 74872 KB Output is correct
11 Correct 934 ms 118892 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 1524 KB Output is correct
2 Correct 89 ms 1400 KB Output is correct
3 Correct 85 ms 1444 KB Output is correct
4 Correct 105 ms 1476 KB Output is correct
5 Correct 177 ms 2044 KB Output is correct
6 Correct 910 ms 69724 KB Output is correct
7 Correct 1039 ms 71672 KB Output is correct
8 Correct 1191 ms 67704 KB Output is correct
9 Correct 1556 ms 71800 KB Output is correct
10 Correct 827 ms 67804 KB Output is correct
11 Correct 965 ms 67832 KB Output is correct
12 Correct 579 ms 67832 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 512 KB Output is correct
2 Correct 18 ms 512 KB Output is correct
3 Correct 22 ms 504 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 9 ms 512 KB Output is correct
6 Correct 18 ms 504 KB Output is correct
7 Correct 20 ms 504 KB Output is correct
8 Correct 21 ms 512 KB Output is correct
9 Correct 21 ms 504 KB Output is correct
10 Correct 21 ms 512 KB Output is correct
11 Correct 21 ms 512 KB Output is correct
12 Correct 11 ms 512 KB Output is correct
13 Correct 43 ms 1024 KB Output is correct
14 Correct 52 ms 1024 KB Output is correct
15 Correct 23 ms 1152 KB Output is correct
16 Correct 19 ms 2304 KB Output is correct
17 Correct 35 ms 1144 KB Output is correct
18 Correct 45 ms 1088 KB Output is correct
19 Correct 37 ms 1152 KB Output is correct
20 Correct 39 ms 1656 KB Output is correct
21 Correct 30 ms 1144 KB Output is correct
22 Correct 25 ms 2296 KB Output is correct
23 Correct 1628 ms 63352 KB Output is correct
24 Correct 945 ms 63356 KB Output is correct
25 Correct 972 ms 63352 KB Output is correct
26 Correct 688 ms 59920 KB Output is correct
27 Correct 675 ms 63456 KB Output is correct
28 Correct 1059 ms 63352 KB Output is correct
29 Correct 923 ms 63224 KB Output is correct
30 Correct 749 ms 60408 KB Output is correct
31 Correct 982 ms 59512 KB Output is correct
32 Correct 968 ms 61432 KB Output is correct
33 Correct 83 ms 1024 KB Output is correct
34 Correct 132 ms 6008 KB Output is correct
35 Correct 762 ms 63324 KB Output is correct
36 Correct 1573 ms 63328 KB Output is correct
37 Correct 767 ms 67448 KB Output is correct
38 Correct 1556 ms 184568 KB Output is correct
39 Correct 667 ms 63964 KB Output is correct
40 Correct 1218 ms 63224 KB Output is correct
41 Correct 803 ms 60792 KB Output is correct
42 Correct 921 ms 74872 KB Output is correct
43 Correct 934 ms 118892 KB Output is correct
44 Correct 73 ms 1524 KB Output is correct
45 Correct 89 ms 1400 KB Output is correct
46 Correct 85 ms 1444 KB Output is correct
47 Correct 105 ms 1476 KB Output is correct
48 Correct 177 ms 2044 KB Output is correct
49 Correct 910 ms 69724 KB Output is correct
50 Correct 1039 ms 71672 KB Output is correct
51 Correct 1191 ms 67704 KB Output is correct
52 Correct 1556 ms 71800 KB Output is correct
53 Correct 827 ms 67804 KB Output is correct
54 Correct 965 ms 67832 KB Output is correct
55 Correct 579 ms 67832 KB Output is correct
56 Correct 107 ms 2036 KB Output is correct
57 Correct 215 ms 2248 KB Output is correct
58 Correct 347 ms 2920 KB Output is correct
59 Correct 1648 ms 70564 KB Output is correct
60 Correct 2645 ms 70944 KB Output is correct
61 Correct 1381 ms 70136 KB Output is correct
62 Correct 1168 ms 73544 KB Output is correct
63 Correct 2377 ms 76124 KB Output is correct
64 Correct 1610 ms 74172 KB Output is correct
65 Correct 1332 ms 69752 KB Output is correct
66 Correct 1692 ms 71696 KB Output is correct
67 Correct 1572 ms 84992 KB Output is correct
68 Correct 1193 ms 109276 KB Output is correct
69 Correct 2285 ms 131908 KB Output is correct