# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
951427 |
2024-03-22T00:05:49 Z |
djs100201 |
Seats (IOI18_seats) |
C++17 |
|
0 ms |
0 KB |
#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;
}
Compilation message
seats.cpp:12:37: warning: integer overflow in expression of type 'll' {aka 'int'} results in '1321730048' [-Woverflow]
12 | const ll n_ =2e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
| ~~~~~~~~^~~~~~~~~
seats.cpp: In member function 'node lazy_seg::init(ll, ll, ll)':
seats.cpp:47:17: error: 'F' was not declared in this scope
47 | tree[N].val={F[N],S[N]};
| ^
seats.cpp:47:22: error: 'S' was not declared in this scope
47 | tree[N].val={F[N],S[N]};
| ^
seats.cpp:47:26: error: no match for 'operator=' (operand types are 'P' {aka 'std::pair<int, int>'} and '<brace-enclosed initializer list>')
47 | tree[N].val={F[N],S[N]};
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from seats.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<int, int>&]'
390 | operator=(typename conditional<
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<int, int>&, const std::__nonesuch&>::type' {aka 'const std::pair<int, int>&'}
390 | operator=(typename conditional<
| ~~~~~~~~~~~~~~~~~~~~~
391 | __and_<is_copy_assignable<_T1>,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
392 | is_copy_assignable<_T2>>::value,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
393 | const pair&, const __nonesuch&>::type __p)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<int, int>&&]'
401 | operator=(typename conditional<
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<int, int>&&, std::__nonesuch&&>::type' {aka 'std::pair<int, int>&&'}
401 | operator=(typename conditional<
| ~~~~~~~~~~~~~~~~~~~~~
402 | __and_<is_move_assignable<_T1>,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
403 | is_move_assignable<_T2>>::value,
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
404 | pair&&, __nonesuch&&>::type __p)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
418 | operator=(const pair<_U1, _U2>& __p)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: template argument deduction/substitution failed:
seats.cpp:47:26: note: couldn't deduce template parameter '_U1'
47 | tree[N].val={F[N],S[N]};
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from seats.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
430 | operator=(pair<_U1, _U2>&& __p)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note: template argument deduction/substitution failed:
seats.cpp:47:26: note: couldn't deduce template parameter '_U1'
47 | tree[N].val={F[N],S[N]};
| ^