| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 674391 | alvingogo | 자리 배치 (IOI18_seats) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
int h,w;
vector<vector<int> > val;
vector<pair<int,int> > y;
int n;
struct ST{
struct no{
int mn=0,cnt=0,tag=0;
};
vector<no> st;
void init(int x){
st.resize(4*x);
}
void upd(int v,int k){
st[v].mn+=k;
st[v].tag+=k;
}
void pudo(int v){
upd(2*v+1,st[v].tag);
upd(2*v+2,st[v].tag);
st[v].tag=0;
}
void pull(int v){
st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
st[v].cnt=0;
if(st[2*v+1].mn==st[v].mn){
st[v].cnt+=st[2*v+1].cnt;
}
if(st[2*v+2].mn==st[v].mn){
st[v].cnt+=st[2*v+2].cnt;
}
}
void update(int v,int L,int R,int l,int r,int k){
if(L==l && r==R){
upd(v,k);
return;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
update(2*v+1,L,m,l,r,k);
}
else if(l>m){
update(2*v+2,m+1,R,l,r,k);
}
else{
update(2*v+1,L,m,l,m,k);
update(2*v+2,m+1,R,m+1,r,k);
}
pull(v);
}
int query(){
return st[0].cnt;
}
}st;
void check(int a,int b,int c,int d,int k){
vector<int> g{a,b,c,d};
sort(g.begin(),g.end());
st.update(0,0,n-1,g[0],g[1],k);
st.update(0,0,n-1,g[2],g[3],k);
}
inline void chg(int i,int j,int t){
check(val[i][j],val[i+1][j],val[i+1][j+1],val[i][j+1],1);
}
void give_initial_chart(int a,int b,int r[],int c[]){
h=a;
w=b;
val.resize(h+2,vector<int>(w+2,1e9));
st.init(h*w);
n=h*w;
for(int i=0;i<h*w;i++){
r[i]++;
c[i]++;
val[r[i]][c[i]]=i;
y.push_back({r[i],c[i]});
}
for(int i=0;i<=h;i++){
for(int j=0;j<=w;j++){
chg(i,j,1);
}
}
}
const int dx[4]={0,0,-1,-1};
const int dy[4]={0,-1,0,-1};
int swap_seats(int a,int b){
auto c=y[a];
auto d=y[b];
for(int i=0;i<4;i++){
chg(c.fs+dx[i],c.sc+dy[i],-1);
}
swap(val[c.fs][c.sc],val[d.fs][d.sc]);
for(int i=0;i<4;i++){
chg(c.fs+dx[i],c.sc+dy[i],1);
}
swap(y[a],y[b]);
return st.query();
}