| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 176077 | kishtarn555 | 자리 배치 (IOI18_seats) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "seats.h"
#include <iostream>
#include <algorithm>
using namespace std;
#define minimos 0
#define maximos 1
vector< vector<int> > mat;
vector<int> r;
vector<int> c;
int HH,WW;
struct st {
st *l, *r;
int m,f;
int M,F;
int lz1,lz2;
};
st *bl,*wt;
st* build (int l, int r, int type) {
st * n = new st;
n->lz1=0;
n->lz2=0;
n->m=0;
n->f=1;
n->M=0;
n->F=1;
n->l=n->r=NULL;
if (l==r)
return n;
n->l = build(l, (l+r)/2, type);
n->r = build((l+r)/2+1,r, type);
n->f = n->l->f+ n->r->f;
n->F = n->l->F+ n->r->F;
return n;
}
int tmp[4];
void inline push(st *cur) {
cur->m+=cur->lz1;
cur->M+=cur->lz2;
if (cur->l) {
cur->l->lz1+=cur->lz1;
cur->l->lz2+=cur->lz2;
cur->r->lz1+=cur->lz1;
cur->r->lz2+=cur->lz2;
sdkj
}
cur->lz1=0;
cur->lz2=0;
}
void update (st * cur, int l,int r, const int i, const int j,const int v1,const int v2) {
push(cur);
if (j < l || r < i)
return;
if (i<=l && r<=j) {
cur->lz1+=v1;
cur->lz2+=v2;
push(cur);
return;
}
int m =(l+r)/2;
update(cur->l, l,m, i,j,v1,v2);
update(cur->r, m+1,r, i,j,v1,v2);
if (cur->l->M < cur->r->M) {
cur->M=cur->l->M;
cur->F=cur->l->F;
cur->m=cur->l->m;
cur->f=cur->l->f;
}else if (cur->l->M > cur->r->M) {
cur->M=cur->r->M;
cur->F=cur->r->F;
cur->m=cur->r->m;
cur->f=cur->r->f;
}else {
if (cur->l->m < cur->r->m) {
cur->M=cur->l->M;
cur->F=cur->l->F;
cur->m=cur->l->m;
cur->f=cur->l->f;
} else if (cur->l->m > cur->r->m) {
cur->M=cur->r->M;
cur->F=cur->r->F;
cur->m=cur->r->m;
cur->f=cur->r->f;
} else {
cur->M=cur->r->M;
cur->F=cur->r->F+cur->l->F;
cur->m=cur->r->m;
cur->f=cur->r->f+cur->l->f;
}
}
}
void print(st * n) {
push(n);
if (n->l) {
print(n->l);
print(n->r);
} else {
// cout <<"{"<< n->m <<","<<n->f<<"}"<<"{"<<n->M<<","<<n->F <<"}";
// cout << endl;
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
HH=H;
WW=W;
r=R;
c=C;
mat.resize(H+2);
for (int i =0; i < H+2; i++) {
mat[i].resize(W+2);
}
for (int i =0; i < H+2; i++) {
for (int j =0; j< W+2; j++)
mat[i][j]=H*W;
}
for (int i =0; i < H*W; i++) {
mat[ R[i]+1 ][C[i]+1]=i;
}
bl=build(0,H*W-1,minimos);
for (int i =1; i < H+2; i++) {
for (int j =1; j < W+2; j++) {
tmp[0]=mat[i-1][j-1];
tmp[1]=mat[i-1][j];
tmp[2]=mat[i][j-1];
tmp[3]=mat[i][j];
sort(tmp,tmp+4);
// cout << mat[i][j]<<"::"<<tmp[0]<<","<<tmp[1]<<","<<tmp[2]<<","<<tmp[3]<<","<<tmp[4]<<endl;
int ind=2;
if (tmp[2]==H*W)ind=1;
if (tmp[1]==H*W)ind=0;
// cout << tmp[0]<<","<<tmp[1]-1<<";1 pintado"<<endl;
// if (ind==2)
update(bl, 0, H*W-1, tmp[0],tmp[1]-1,1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, H*W-1, tmp[ind],tmp[ind+1]-1,0,1);
}
}
}
// for (int i =0; i <)
// cout <<"{"<< bl->m <<","<<bl->f<<"}"<<"{"<<bl->M<<","<<bl->F <<"}";
// cout << endl;
// cout << endl;
print(bl);
}
int swap_seats(int a, int b) {
int r1=r[a]+1,c1=c[a]+1;
int r2=r[b]+1,c2=c[b]+1;
// cout <<"______________"<<endl;
// cout << r1 << ","<<c1<<endl;
// cout << r2 << ","<<c2<<endl;
swap(r[a],r[b]);
swap(c[a],c[b]);
for (int i =0; i < 2; i++){
for (int j = 0; j < 2; j++) {
tmp[0]=mat[i+r1-1][j+c1-1];
tmp[1]=mat[i+r1-1][j+c1];
tmp[2]=mat[i+r1] [j+c1-1];
tmp[3]=mat[i+r1] [j+c1];
sort(tmp,tmp+4);
int ind=2;
if (tmp[2]==HH*WW)ind=1;
if (tmp[1]==HH*WW)ind=0;
update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,-1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,-1);
}
}
}
for (int i =0; i < 2; i++){
for (int j = 0; j < 2; j++) {
tmp[0]=mat[i+r2-1][j+c2-1];
tmp[1]=mat[i+r2-1][j+c2];
tmp[2]=mat[i+r2] [j+c2-1];
tmp[3]=mat[i+r2] [j+c2];
sort(tmp,tmp+4);
int ind=2;
if (tmp[2]==HH*WW)ind=1;
if (tmp[1]==HH*WW)ind=0;
update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,-1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,-1);
}
}
}
swap(mat[r1][c1] ,mat[r2][c2]);
for (int i =0; i < 2; i++){
for (int j = 0; j < 2; j++) {
tmp[0]=mat[i+r1-1][j+c1-1];
tmp[1]=mat[i+r1-1][j+c1];
tmp[2]=mat[i+r1] [j+c1-1];
tmp[3]=mat[i+r1] [j+c1];
sort(tmp,tmp+4);
int ind=2;
if (tmp[2]==HH*WW)ind=1;
if (tmp[1]==HH*WW)ind=0;
update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,1);
}
}
}
for (int i =0; i < 2; i++){
for (int j = 0; j < 2; j++) {
tmp[0]=mat[i+r2-1][j+c2-1];
tmp[1]=mat[i+r2-1][j+c2];
tmp[2]=mat[i+r2] [j+c2-1];
tmp[3]=mat[i+r2] [j+c2];
sort(tmp,tmp+4);
int ind=2;
if (tmp[2]==HH*WW)ind=1;
if (tmp[1]==HH*WW)ind=0;
update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,1);
}
}
}
int t =0;
if (bl->M ==0 && bl->m == 4) {
t= bl->f;
}
return t;
}