이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "seats.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
const int N=4e6+5;
const int INF=1e9+5;
pair<int,int> A[N];
struct node{
int mxx, mnx, mxy,mny;
};
struct ST{
node tree[N];
node combine(node a, node b){
return {max(a.mxx,b.mxx),min(a.mnx,b.mnx),max(a.mxy,b.mxy),min(a.mny,b.mny)};
}
void build(int x, int l, int r, vector<pair<int,int>> &vec){
if(l==r){
tree[x]={vec[l].fr,vec[l].fr,vec[l].sc,vec[l].sc};
return;
}
int md=(l+r)/2;
build(2*x,l,md,vec);
build(2*x+1,md+1,r,vec);
tree[x]=combine(tree[2*x],tree[2*x+1]);
}
void update(int x, int l, int r, int i, pair<int,int> val){
if(l==r){
tree[x]={val.fr,val.fr,val.sc,val.sc};
return;
}
int md=(l+r)/2;
if(i<=md) update(2*x ,l ,md,i,val);
else update(2*x+1,md+1,r ,i,val);
tree[x]=combine(tree[2*x],tree[2*x+1]);
}
int find_minx(int x, int l, int r, int lx, int rx){
if(l>rx || r<lx) return INF;
if(lx<=l && r<=rx) return tree[x].mnx;
int md=(l+r)/2;
//cout<<l<<' '<<r<<' '<<lx<<' '<<rx<<endl;
return min(find_minx(2*x,l,md,lx,rx),find_minx(2*x+1,md+1,r,lx,rx));
}
int find_maxx(int x, int l, int r, int lx, int rx){
if(l>rx || r<lx) return -INF;
if(lx<=l && r<=rx) return tree[x].mxx;
int md=(l+r)/2;
return max(find_maxx(2*x,l,md,lx,rx),find_maxx(2*x+1,md+1,r,lx,rx));
}
int find_miny(int x, int l, int r, int lx, int rx){
if(l>rx || r<lx) return INF;
if(lx<=l && r<=rx) return tree[x].mny;
int md=(l+r)/2;
return min(find_miny(2*x,l,md,lx,rx),find_miny(2*x+1,md+1,r,lx,rx));
}
int find_maxy(int x, int l, int r, int lx, int rx){
if(l>rx || r<lx) return -INF;
if(lx<=l && r<=rx) return tree[x].mxy;
int md=(l+r)/2;
return max(find_maxy(2*x,l,md,lx,rx),find_maxy(2*x+1,md+1,r,lx,rx));
}
} st;
int k;
int h,w;
vector<int> R,C;
void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
R=r,C=c;
h=H,w=W;
int n=1;
while(n<H*W) n*=2;
vector<pair<int,int>> v(n);
for(int i=0;i<H*W;i++)
v[i]={R[i],C[i]};
k=n;
st.build(1,0,k-1,v);
}
int swap_seats(int a, int b) {
st.update(1,0,k-1,a,{R[b],C[b]});
st.update(1,0,k-1,b,{R[a],C[a]});
swap(R[a],R[b]);
swap(C[a],C[b]);
int id=1,ans=1;
while(id<h*w){
int l=st.find_minx(1,0,k-1,0,id);
int r=st.find_maxx(1,0,k-1,0,id);
int d=st.find_miny(1,0,k-1,0,id);
int u=st.find_maxy(1,0,k-1,0,id);
//cout<<R[0]<<' '<<C[0]<<endl;
//cout<<l<<' '<<r<<' '<<d<<' '<<u<<' ';
//cout<<id<<endl;
if((r-l+1)*(u-d+1)-1==id) ans++,id++;
else id=(r-l+1)*(u-d+1)-1;
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |