| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1052666 | Ahmed57 | Seats (IOI18_seats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
vector<int> c,r;
int pos[1001][1001];
int h,w;
int cst[1001][1001];
pair<pair<int,int>,int> seg[4000001];
pair<int,int> lazy[4000001];
void build(int p,int l,int r){
if(l==r){
seg[p] = {{0,0},1};
return ;
}
int md = (l+r)/2;
build(p*2,l,md);
build(p*2+1,md+1,r);
seg[p].first = min(seg[p*2].first,seg[p*2+1].first);
seg[p].second = (seg[p*2].first==seg[p].first?seg[p*2].second:0)+(seg[p*2+1].first==seg[p].first?seg[p*2+1].second:0);
}
void prop(int p,int l,int r){
seg[p].first.first+=lazy[p].first;
seg[p].first.second+=lazy[p].second;
if(l!=r){
lazy[p*2].first+=lazy[p].first;
lazy[p*2].second+=lazy[p].second;
lazy[p*2+1].first+=lazy[p].first;
lazy[p*2+1].second+=lazy[p].second;
}
lazy[p] = {0,0};
}
void update(int p,int l,int r,int lq,int rq,int val1,int val2){
prop(p,l,r);
if(l>=lq&&r<=rq){
lazy[p] = {val1,val2};
prop(p,l,r);
return ;
}
if(r<lq||l>rq)return ;
int md = (l+r)/2;
update(p*2,l,md,lq,rq,val1,val2);
update(p*2+1,md+1,r,lq,rq,val1,val2);
seg[p].first = min(seg[p*2].first,seg[p*2+1].first);
seg[p].second = (seg[p*2].first==seg[p].first?seg[p*2].second:0)+(seg[p*2+1].first==seg[p].first?seg[p*2+1].second:0);
}
int cn(int st1,int st2,int x){
int na = 0;
for(int i = st1;i<st1+2;i++){
for(int j = st2;j<st2+2;j++){
if(i<0||j<0||i>=h||j>=w){
continue;
}
if(pos[i][j]<x)na++;
}
}
return na;
}
int dx[4] = {0,0,1,1};
int dy[4] = {0,1,0,1};
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
h = H;
w = W;
for(int i = 0;i<H*W;i++){
c.push_back(C[i]);
r.push_back(R[i]);
}
for(int i = 0;i<H*W;i++){
pos[r[i]][c[i]] = i;
}
build(1,0,H*W-1);
for(int i = 0;i<H*W;i++){
for(int j = 0;j<4;j++){
int lol = cn(r[i]-dx[j],c[i]-dy[j],i);
if(lol==1){
update(1,0,h*w-1,i,h*w-1,-1,0);
}if(lol==3){
update(1,0,h*w-1,i,h*w-1,0,-1);
}
lol = cn(r[i]-dx[j],c[i]-dy[j],i+1);
if(lol==1){
update(1,0,h*w-1,i,h*w-1,1,0);
}if(lol==3){
update(1,0,h*w-1,i,h*w-1,0,1);
}
}
}
}
int swap_seats(int a, int b){
set<pair<int,int>> s;
for(int x = -1;x<=1;x++){
for(int y = -1;y<=1;y++){
if(r[a]+x>=0&&r[a]+x<h&&c[a]+y>=0&&c[a]+y<w){
s.insert({r[a]+x,c[a]+y});
}
if(r[b]+x>=0&&r[b]+x<h&&c[b]+y>=0&&c[b]+y<w){
s.insert({r[b]+x,c[b]+y});
}
}
}
for(auto e:s){
int i = pos[e.first][e.second];
for(int j = 0;j<4;j++){
int lol = cn(r[i]-dx[j],c[i]-dy[j],i);
if(lol==1){
update(1,0,h*w-1,i,h*w-1,1,0);
}if(lol==3){
update(1,0,h*w-1,i,h*w-1,0,1);
}
lol = cn(r[i]-dx[j],c[i]-dy[j],i+1);
if(lol==1){
update(1,0,h*w-1,i,h*w-1,-1,0);
}if(lol==3){
update(1,0,h*w-1,i,h*w-1,0,-1);
}
}
}
swap(c[a],c[b]);
swap(r[a],r[b]);
swap(pos[r[a]][c[a]],pos[r[b]][c[b]]);
for(auto e:s){
int i = pos[e.first][e.second];
for(int j = 0;j<4;j++){
int lol = cn(r[i]-dx[j],c[i]-dy[j],i);
if(lol==1){
update(1,0,h*w-1,i,h*w-1,-1,0);
}if(lol==3){
update(1,0,h*w-1,i,h*w-1,0,-1);
}
lol = cn(r[i]-dx[j],c[i]-dy[j],i+1);
if(lol==1){
update(1,0,h*w-1,i,h*w-1,1,0);
}if(lol==3){
update(1,0,h*w-1,i,h*w-1,0,1);
}
}
}
return seg[1].second;
}
int main(){
give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1,
1, 2, 2});
cout<<swap_seats(0,5)<<endl;
}