제출 #103649

#제출 시각아이디문제언어결과실행 시간메모리
103649figter001자리 배치 (IOI18_seats)C++17
25 / 100
4077 ms73692 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int nax = 1010; const int kax = nax*nax; struct node{ int u,d,a,b; }seg[3*kax]; pair<int,int> p[kax]; int at,h,w,l,r,cnt,n; void build(int n,int s,int e){ if(s == e){ seg[n] = {p[s-1].first,p[s-1].first,p[s-1].second,p[s-1].second}; return; } build(n*2,s,(s+e)/2); build(n*2+1,(s+e)/2+1,e); seg[n] = {min(seg[n*2].u,seg[n*2+1].u) , max(seg[n*2].d,seg[n*2+1].d) , min(seg[n*2].a,seg[n*2+1].a) , max(seg[n*2].b,seg[n*2+1].b) }; } void update(int n,int s,int e){ if(s == e){ seg[n] = {p[s-1].first,p[s-1].first,p[s-1].second,p[s-1].second}; return; } if((s+e)/2 >= at) update(n*2,s,(s+e)/2); if((s+e)/2+1 <= at) update(n*2+1,(s+e)/2+1,e); seg[n] = {min(seg[n*2].u,seg[n*2+1].u) , max(seg[n*2].d,seg[n*2+1].d) , min(seg[n*2].a,seg[n*2+1].a) , max(seg[n*2].b,seg[n*2+1].b) }; } node get(int n,int s,int e){ if(s >= l && e <= r) return seg[n]; node x,y,z; x = y = {(int)1e9,0,(int)1e9,0}; if((s+e)/2 >= l) x = get(n*2,s,(s+e)/2); if((s+e)/2+1 <= r) y = get(n*2+1,(s+e)/2+1,e); z = {min(x.u,y.u) , max(x.d,y.d) , min(x.a,y.a) , max(x.b,y.b) }; return z; } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { for(int i=0;i<H*W;i++) p[i] = {R[i],C[i]}; h = H; w = W; n = h*w; build(1,1,n); } int swap_seats(int a, int b) { swap(p[a],p[b]); at = a+1; update(1,1,n); at = b+1; update(1,1,n); int ans = 0,cur = 0; l = 1; while(1){ if(cur >= h*w) break; r = cur+1; node g = get(1,1,n); int u = g.u; int d = g.d; int a = g.a; int b = g.b; if((d - u + 1) * (b - a + 1) == cur + 1){ ans++; cur++; }else{ cur = (d - u + 1) * (b - a + 1) - 1; } } return ans; }
#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...