제출 #951240

#제출 시각아이디문제언어결과실행 시간메모리
951240djs100201자리 배치 (IOI18_seats)C++17
0 / 100
334 ms262144 KiB
#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 = long long; 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,A; vector<P>lazy; void start(int n) { // 0~n까지 쓰겠다. tree.resize(n * 4); lazy.resize(n * 4); A.resize(n * 4); } P add(P A,P B){ P ret=A; ret.first+=B.first,ret.second+=B.second; return ret; } node init(ll N, ll s, ll e) { if (s == e)return tree[N]=A[s]; 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]); } /*ll f(ll N, ll s, ll e, ll l, ll r) { update_lazy(N, s, e); if (l > e || r < s) return 0; if (l <= s && e <= r) return tree[N]; ll mid = (s + e) / 2; return f(N * 2, s, mid, l, r) + f(N * 2 + 1, mid + 1, e, l, r); } */ }; vector<vector<int>>arr; 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) { arr.resize(H); for(int i=0;i<H;i++)arr[i].resize(W); n=H,m=W; N=R,M=C; seg.start(n*m); 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); //cout<<i<<' '<<j<<' '<<F[0]<<' '<<S[0]<<endl; } for(int i=0;i<n*m;i++){ if(i)F[i]+=F[i-1],S[i]+=S[i-1]; seg.A[i].val={F[i],S[i]}; seg.A[i].cnt=1; //cout<<i<<' '<<F[i]<<' '<<S[i]<<endl; } seg.init(1,0,n*m-1); //cout<<seg.tree[1].cnt<<endl; } void query(int y,int x,int val){ 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)); ll ff=0; 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) { //cout<<N[a]<<' '<<M[a]<<endl; //cout<<N[b]<<' '<<M[b]<<endl; 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); return seg.tree[1].cnt; }

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In function 'void query(int, int, int)':
seats.cpp:240:6: warning: unused variable 'ff' [-Wunused-variable]
  240 |   ll ff=0;
      |      ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...