| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 107451 | kig9981 | 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;
const int SZ=1<<20, dx[]={-1,0,1,0}, dy[]={0,-1,0,1};
vector<pair<int,int>> P;
pair<int,int> tree[2*SZ], lazy[2*SZ];
int N, M, tcnt[2*SZ], idx[100000];
void lazy_propagation(int bit, int s, int e)
{
tree[bit].first+=lazy[bit].first;
tree[bit].second+=lazy[bit].second;
if(s<e) {
lazy[2*bit].first+=lazy[bit].first;
lazy[2*bit].second+=lazy[bit].second;
lazy[2*bit+1].first+=lazy[bit].first;
lazy[2*bit+1].second+=lazy[bit].second;
}
lazy[bit]={0,0};
}
void add_tree(int n, pair<int,int> v, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(bit,s,e);
if(e<n) return;
if(n<=s) {
tree[bit].first+=v.first;
tree[bit].second+=v.second;
if(s<e) {
lazy[2*bit].first+=v.first;
lazy[2*bit].second+=v.second;
lazy[2*bit+1].first+=v.first;
lazy[2*bit+1].second+=v.second;
}
return;
}
add_tree(n,v,2*bit,s,m);
add_tree(n,v,2*bit+1,m+1,e);
tree[bit]=min(tree[2*bit],tree[2*bit+1]);
tcnt[bit]=(tree[bit]==tree[2*bit] ? tcnt[2*bit]:0)+(tree[bit]==tree[2*bit+1] ? tcnt[2*bit+1]:0);
}
bool valid_coord(int x, int y)
{
return 0<=x && x<N && 0<=y && y<M;
}
int convert(int x, int y)
{
return x*M+y;
}
pair<int,int> get_corner(int x, int y, int i)
{
pair<int,int> ret;
for(int k=0;k<4;k++) {
if(valid_coord(x+dx[k],y+dy[k]) && valid_coord(x+dx[(k+1)&3],y+dy[(k+1)&3]) && idx[convert(x+dx[k],y+dy[k])]<=i && idx[convert(x+dx[(k+1)&3],y+dy[(k+1)&3])]<=i && idx[convert(x,y)]>i) {
ret.second++;
}
else if((!valid_coord(x+dx[k],y+dy[k]) || idx[convert(x+dx[k],y+dy[k])]>i) && (!valid_coord(x+dx[(k+1)&3],y+dy[(k+1)&3]) || idx[convert(x+dx[(k+1)&3],y+dy[(k+1)&3])]>i) && idx[convert(x,y)]<=i) {
ret.first++;
}
}
return ret;
}
pair<int,int> get_diff(int i)
{
pair<int,int> ret, temp;
int x=P[i].first, y=P[i].second;
temp=get_corner(x,y,i);
ret.first+=temp.first;
ret.second+=temp.second;
temp=get_corner(x,y,i-1);
ret.first-=temp.first;
ret.second-=temp.second;
for(int k=0;k<4;k++) {
if(valid_coord(x+dx[k],y+dy[k])) {
temp=get_corner(x+dx[k],y+dy[k],i);
ret.first+=temp.first;
ret.second+=temp.second;
temp=get_corner(x+dx[k],y+dy[k],i-1);
ret.first-=temp.first;
ret.second-=temp.second;
}
}
return ret;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
P.resize(H*W);
N=H; M=W;
for(int i=0;i<H*W;i++) {
P[i]={R[i],C[i]};
idx[convert(R[i],C[i])]=i;
tcnt[SZ+i]=1;
}
tree[SZ]=get_diff(0);
for(int i=1;i<H*W;i++) {
tree[SZ+i]=get_diff(i);
tree[SZ+i].first+=tree[SZ+i-1].first;
tree[SZ+i].second+=tree[SZ+i-1].second;
}
for(int i=H*W;i<SZ;i++) tree[SZ+i]=make_pair(0x1fffffff,0x1fffffff);
for(int i=SZ-1;i;i--) {
tree[i]=min(tree[2*i],tree[2*i+1]);
tcnt[i]=(tree[i]==tree[2*i] ? tcnt[2*i]:0)+(tree[i]==tree[2*i+1] ? tcnt[2*i+1]:0);
}
}
int swap_seat(int a, int b)
{
pair<int,int> temp;
int x1=P[a].first, y1=P[a].second, x2=P[b].first, y2=P[b].second;
temp=get_diff(a); temp.first*=-1; temp.second*=-1;
add_tree(a,temp);
temp=get_diff(b); temp.first*=-1; temp.second*=-1;
add_tree(b,temp);
for(int k=0;k<4;k++) {
if(valid_coord(x1+dx[k],y1+dy[k])) {
temp=get_diff(convert(x1+dx[k],y1+dy[k])); temp.first*=-1; temp.second*=-1;
add_tree(convert(x1+dx[k],y1+dy[k]),temp);
}
if(valid_coord(x2+dx[k],y2+dy[k])) {
temp=get_diff(convert(x2+dx[k],y2+dy[k])); temp.first*=-1; temp.second*=-1;
add_tree(convert(x2+dx[k],y2+dy[k]),temp);
}
}
swap(P[a],P[b]);
swap(idx[convert(P[a].first,P[a].second)],idx[convert(P[b].first,P[b].second)]);
add_tree(a,get_diff(a));
add_tree(b,get_diff(b));
for(int k=0;k<4;k++) {
if(valid_coord(x1+dx[k],y1+dy[k])) {
add_tree(convert(x1+dx[k],y1+dy[k]),get_diff(convert(x1+dx[k],y1+dy[k])));
}
if(valid_coord(x2+dx[k],y2+dy[k])) {
add_tree(convert(x2+dx[k],y2+dy[k]),get_diff(convert(x2+dx[k],y2+dy[k])));
}
}
return tree[1]==make_pair(4,0) ? tcnt[1]:0;
}