| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 131602 | rondojim | 자리 배치 (IOI18_seats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
struct segtree{
struct node{
int cnt, mn, lz;
node(){
mn = 0;
cnt = 1;
lz = 0;
}
node operator+(const node &p)const{
node ret;
ret.mn = min(mn, p.mn);
ret.cnt = 0;
if (ret.mn == mn){
ret.cnt += cnt;
}
if (ret.mn == p.mn){
ret.cnt += p.cnt;
}
ret.lz = 0;
return ret;
}
}seg[4 * N];
void update_lazy(int idx){
seg[2 * idx].mn += seg[idx].lz;
seg[2 * idx].lz += seg[idx].lz;
seg[2 * idx + 1].mn += seg[idx].lz;
seg[2 * idx + 1].lz += seg[idx].lz;
seg[idx].lz = 0;
}
void update(int idx, int l, int r, int sl, int sr, int val){
//cout << "update" << idx << " " << l << " " << r << " " << sl << " " << sr << " " << val << endl;
if(l > sr || r < sl){
return;
}
if(sl <= l && r <= sr){
seg[idx].mn += val;
seg[idx].lz += val;
return;
}
update_lazy(idx);
int mid = (l + r) >> 1;
update(2 * idx, l, mid, sl, sr, val);
update(2 * idx + 1, mid + 1, r, sl, sr, val);
seg[idx] = seg[2 * idx] + seg[2 * idx + 1];
}
int get(){
if(seg[1].mn == 2){
return seg[1].cnt;
}
return 0;
}
}st;
pair<int, int> p[N], mx[N], mn[N];
int ptr[N];
int h, w;
int ans = 0;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H;
w = W;
for(int i = 0; i < (int)R.size(); i++){
p[i].first = R[i];
p[i].second = C[i];
}
if(h == 1){
for(int i = 0; i < w; i++){
ptr[p[i].second] = i;
}
for(int i = 0; i < w; i++){
//cout << i << " i" << endl;
if(p[i].second == H * W - 1){
st.update(1, 0, w - 1, i, w - 1, 1);
continue;
}
if(p[i].second == 0){
st.update(1, 0, w - 1, i, w - 1, 1);
}
//cout << p[i].second + 1 << " p[i].second" << endl;
int j = ptr[p[i].second + 1];
//cout << j<< " j" << endl;
st.update(1, 0, w - 1, min(i, j), max(i, j) - 1, 1);
}
return;
}
mx[0].first = p[0].first;
mx[0].second = p[0].second;
mn[0].first = p[0].first;
mn[0].second = p[0].second;
ans++;
for(int i = 1; i < H * W; i++){
mx[i].first = max(mx[i - 1].first, p[i].first);
mx[i].second = max(mx[i - 1].second, p[i].second);
mn[i].first = min(mn[i - 1].first, p[i].first);
mn[i].second = min(mn[i - 1].second, p[i].second);
if((mx[i].first - mn[i].first + 1) * (mx[i].second - mn[i].second + 1) == i + 1){
ans++;
}
}
}
int swap_seats(int a, int b){
if(h == 1){
if(w == 1){
return 1;
}
if(a == b){
return st.get();
}
if(a > b){
swap(a, b);
}
//cout << p[a].second << " p " << p[b].second << endl;
if(p[a].second + 1 != p[b].second){
int x, y;
if(p[a].second != w - 1){
x = ptr[p[a].second + 1];
//cout << x << " x" << endl;
st.update(1, 0, w - 1, min(a, x), max(a, x) - 1, -1);
st.update(1, 0, w - 1, min(b, x), max(b, x) - 1, 1);
}
else{
st.update(1, 0, w - 1, a, w - 1, -1);
st.update(1, 0, w - 1, b, w - 1, 1);
}
if(p[b].second != 0){
y = ptr[p[b].second - 1];
//cout << y << " y" << endl;
st.update(1, 0, w - 1, min(b, y), max(b, y) - 1, -1);
st.update(1, 0, w - 1, min(a, y), max(a, y) - 1, 1);
}
else{
st.update(1, 0, w - 1, a, w - 1, 1);
st.update(1, 0, w - 1, b, w - 1, -1);
}
}
if(p[a].second != p[b].second + 1){
int x, y;
if(p[a].second != 0){
x = ptr[p[a].second - 1];
//cout << x << " x" << endl;
st.update(1, 0, w - 1, min(a, x), max(a, x) - 1, -1);
st.update(1, 0, w - 1, min(b, x), max(b, x) - 1, 1);
}
else{
st.update(1, 0, w - 1, a, w - 1, -1);
st.update(1, 0, w - 1, b, w - 1, 1);
}
if(p[b].second != w - 1){
y = ptr[p[b].second + 1];
//cout << y << " y" << endl;
st.update(1, 0, w - 1, min(b, y), max(b, y) - 1, -1);
st.update(1, 0, w - 1, min(a, y), max(a, y) - 1, 1);
}
else{
st.update(1, 0, w - 1, a, w - 1, 1);
st.update(1, 0, w - 1, b, w - 1, -1);
}
}
swap(p[a], p[b]);
swap(ptr[p[a].second], ptr[p[b].second]);
return st.get();
}
swap(p[a], p[b]);
if(a > b){
swap(a, b);
}
for(int i = a; i <= b; i++){
if((mx[i].first - mn[i].first + 1) * (mx[i].second - mn[i].second + 1) == i + 1){
ans--;
}
if(i){
mx[i].first = max(mx[i - 1].first, p[i].first);
mx[i].second = max(mx[i - 1].second, p[i].second);
mn[i].first = min(mn[i - 1].first, p[i].first);
mn[i].second = min(mn[i - 1].second, p[i].second);
}
else{
mx[0].first = p[0].first;
mx[0].second = p[0].second;
mn[0].first = p[0].first;
mn[0].second = p[0].second;
}
if((mx[i].first - mn[i].first + 1) * (mx[i].second - mn[i].second + 1) == i + 1){
ans++;
}
}
return ans;
}
/*int main(){
int H, W;
cin >> H >> W;
vector<int> R, C;
for(int i = 0; i < H * W; i++){
int x;
cin >> x;
R.push_back(x);
}
for(int i = 0; i < H * W; i++){
int x;
cin >> x;
C.push_back(x);
}
give_initial_chart(H, W, R, C);
while(true){
int a, b;
cin >> a >> b;
//cout << swap_seats(a, b) << endl;
}