| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 951427 | djs100201 | 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>
#include "seats.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = int;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =2e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
if(!y)return x;
return gcd(y,x%y);
}
struct node{
P val;
int cnt;
};
node merge(node a, node b){
node ret=a;
if(a.val==b.val){
ret.cnt+=b.cnt;
return ret;
}
if(a.val<b.val)return ret;
return b;
}
P add(P a,P b){
return {a.first+b.first,a.second+b.second};
}
class lazy_seg{
public:
vector<node> tree;
vector<P>lazy;
void start(int n)
{
// 0~n까지 쓰겠다.
tree.resize(n * 4);
lazy.resize(n * 4);
}
node init(ll N, ll s, ll e)
{
if (s == e){
tree[N].val={F[N],S[N]};
tree[N].cnt=1;
}
ll mid = (s + e) / 2;
return tree[N] = merge(init(N * 2, s, mid) , init(N * 2 + 1, mid + 1, e));
}
void update_lazy(ll N, ll s, ll e)
{
if (lazy[N].first==0 && lazy[N].second==0)return;
tree[N].val=add(tree[N].val,lazy[N]);
if (s != e)
{
lazy[N*2]=add(lazy[N*2],lazy[N]);
lazy[N*2+1]=add(lazy[N*2+1],lazy[N]);
}
lazy[N] = {0,0};
}
void update(ll N, ll s, ll e, ll l, ll r, P val)
{
update_lazy(N, s, e);
if (l > e || r < s)
return;
if (l <= s && e <= r)
{
lazy[N] = val;
update_lazy(N, s, e);
return;
}
ll mid = (s + e) / 2;
update(N * 2, s, mid, l, r, val);
update(N * 2 + 1, mid + 1, e, l, r, val);
tree[N]=merge(tree[N*2],tree[N*2+1]);
}
};
vector<vector<int>>arr,bit;
vector<int>F,S,N,M;
ll lim;
void pre_init(int y,int x){
if(y==0){
if(x==0){
F[arr[y][x]]++;
}
else if(x==m){
F[arr[y][x-1]]++;
}
else{
int l=arr[y][x-1],r=arr[y][x];
F[min(l,r)]++,F[max(l,r)]--;
}
}
else if(y==n){
if(x==0){
F[arr[y-1][x]]++;
}
else if(x==m){
F[arr[y-1][x-1]]++;
}
else{
int l=arr[y-1][x-1],r=arr[y-1][x];
F[min(l,r)]++,F[max(l,r)]--;
}
}
else if(x==0){
int u=arr[y-1][x],d=arr[y][x];
F[min(u,d)]++,F[max(u,d)]--;
}
else if(x==m){
int u=arr[y-1][x-1],d=arr[y][x-1];
F[min(u,d)]++,F[max(u,d)]--;
}
else{
//이때부터는 꼭짓점에 인접한 타일이 항상 4개 있는경우 크기에 따라서 정렬해두자.
/*
[0,1]
[2,3]
순서임
*/
vector<P>T;
T.push_back({arr[y-1][x-1],0});
T.push_back({arr[y-1][x],1});
T.push_back({arr[y][x],2});
T.push_back({arr[y][x-1],3});
sort(all(T));
ll ff=0;
for(int i=0;i<4;i++){
auto [a,b]=T[i];
if(i==0)F[a]++;
else if(i==1){
F[a]--;
if((T[0].second^T[1].second)==2){
//마주보는 경우
F[a]+=2;
ff=2;
}
}
else if(i==2){
F[a]-=ff;
S[a]++;
}
else S[a]--;
}
}
}
lazy_seg seg;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
bit.resize(H+1);
for(int i=0;i<=H;i++)bit[i].resize(W+1);
arr.resize(H);
for(int i=0;i<H;i++)arr[i].resize(W);
n=H,m=W;
N=R,M=C;
R.clear(),C.clear();
F.clear(),S.clear();
F.resize(n*m),S.resize(n*m);
//First값과 Second값의 PrefixSum
for(int i=0;i<n*m;i++)arr[R[i]][C[i]]=i;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
pre_init(i,j);
for(int i=0;i<n*m;i++){
if(i)F[i]+=F[i-1],S[i]+=S[i-1];
}
seg.start(n*m);
seg.init(1,0,n*m-1);
}
void query(int y,int x,int val){
if(val<0 && bit[y][x])return;
if(val>0 && !bit[y][x])return;
bit[y][x]^=1;
if(y==0){
if(x==0){
seg.update(1,0,n*m-1,arr[y][x],n*m-1,{val,0});
}
else if(x==m){
seg.update(1,0,n*m-1,arr[y][x-1],n*m-1,{val,0});
}
else{
int l=arr[y][x-1],r=arr[y][x];
if(l>r)swap(l,r);
seg.update(1,0,n*m-1,l,r-1,{val,0});
}
}
else if(y==n){
if(x==0){
seg.update(1,0,n*m-1,arr[y-1][x],n*m-1,{val,0});
}
else if(x==m){
seg.update(1,0,n*m-1,arr[y-1][x-1],n*m-1,{val,0});
}
else{
int l=arr[y-1][x-1],r=arr[y-1][x];
if(l>r)swap(l,r);
seg.update(1,0,n*m-1,l,r-1,{val,0});
}
}
else if(x==0){
int u=arr[y-1][x],d=arr[y][x];
if(d>u)swap(u,d);
seg.update(1,0,n*m-1,d,u-1,{val,0});
}
else if(x==m){
int u=arr[y-1][x-1],d=arr[y][x-1];
if(d>u)swap(u,d);
seg.update(1,0,n*m-1,d,u-1,{val,0});
}
else{
//이때부터는 꼭짓점에 인접한 타일이 항상 4개 있는경우 크기에 따라서 정렬해두자.
/*
[0,1]
[2,3]
순서임
*/
vector<P>T;
T.push_back({arr[y-1][x-1],0});
T.push_back({arr[y-1][x],1});
T.push_back({arr[y][x],2});
T.push_back({arr[y][x-1],3});
sort(all(T));
seg.update(1,0,n*m-1,T[0].first,T[1].first-1,{val,0});
if((T[0].second^T[1].second)==2){
seg.update(1,0,n*m-1,T[1].first,T[2].first-1,{val*2,0});
}
seg.update(1,0,n*m-1,T[2].first,T[3].first-1,{0,val});
}
}
int swap_seats(int a, int b) {
query(N[a],M[a],-1);
query(N[a]+1,M[a],-1);
query(N[a]+1,M[a]+1,-1);
query(N[a],M[a]+1,-1);
query(N[b],M[b],-1);
query(N[b]+1,M[b],-1);
query(N[b]+1,M[b]+1,-1);
query(N[b],M[b]+1,-1);
arr[N[a]][M[a]]=b;
arr[N[b]][M[b]]=a;
swap(N[a],N[b]);
swap(M[a],M[b]);
query(N[a],M[a],1);
query(N[a]+1,M[a],1);
query(N[a]+1,M[a]+1,1);
query(N[a],M[a]+1,1);
query(N[b],M[b],1);
query(N[b]+1,M[b],1);
query(N[b]+1,M[b]+1,1);
query(N[b],M[b]+1,1);
P rec={4,0};
if(seg.tree[1].val==rec)return seg.tree[1].cnt;
else return 0;
}