제출 #943741

#제출 시각아이디문제언어결과실행 시간메모리
943741Lobo자리 배치 (IOI18_seats)C++17
0 / 100
1787 ms110708 KiB
#include "seats.h" #include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() const int maxn = 1e6+10; const int B = 1000; int n, m, col[maxn], row[maxn]; vector<vector<int>> grid; int trmn[4*maxn], trq[4*maxn], lz[4*maxn]; void build(int no, int l, int r) { trq[no] = r-l+1; trmn[no] = 0; if(l == r) return; int lc=2*no,rc=2*no+1,mid=(l+r)/2; build(lc,l,mid); build(rc,mid+1,r); } void flush(int no, int l, int r) { trmn[no]+= lz[no]; if(l != r) { int lc=2*no,rc=2*no+1; lz[lc]+= lz[no]; lz[rc]+= lz[no]; } lz[no] = 0; } void upd(int no, int l, int r, int ll, int rr, int val) { flush(no,l,r); if(l > rr or r < ll) return; if(l >= ll && r <= rr) { lz[no] = val; flush(no,l,r); return; } int lc=2*no,rc=2*no+1,mid=(l+r)/2; upd(lc,l,mid,ll,rr,val); upd(rc,mid+1,r,ll,rr,val); trmn[no] = min(trmn[lc],trmn[rc]); trq[no] = 0; if(trmn[no] == trmn[lc]) trq[no]+= trq[lc]; if(trmn[no] == trmn[rc]) trq[no]+= trq[rc]; } void construct(int i, int j, int dx) { vector<int> times; for(int di = 0; di <= 1; di++) { for(int dj = 0; dj <= 1; dj++) { if(i+di >= 0 && i+di < n && j+dj >= 0 && j+dj < m) { times.pb(grid[i+di][j+dj]); } } } sort(all(times)); for(int i = 0; i < (int) times.size(); i++) { int tl = times[i]; int tr; if(i+1 < (int) times.size()) tr = times[i+1]-1; else tr = n*m-1; if(i+1 == 1) upd(1,0,n*m-1,tl,tr,+1*dx); if(i+1 == 3) upd(1,0,n*m-1,tl,tr,+5*dx); } } void give_initial_chart(int32_t H, int32_t W, std::vector<int32_t> R, std::vector<int32_t> C) { n = H; m = W; grid.resize(n,vector<int>(m)); for(int i = 0; i < n*m; i++) { col[i] = C[i]; row[i] = R[i]; grid[row[i]][col[i]] = i; } build(1,0,n*m-1); for(int i = -1; i < n; i++) { for(int j = -1; j < m; j++) { construct(i,j,1); } } } int32_t swap_seats(int32_t a, int32_t b) { int i,j; set<pair<int,int>> st; i = row[a]; j = col[a]; for(int di = 0; di <= 1; di++) { for(int dj = 0; dj <= 1; dj++) { if(i+di >= -1 && i+di < n && j+dj >= -1 && j+dj < m) { st.insert(mp(i+di,j+dj)); } } } i = row[b]; j = col[b]; for(int di = 0; di <= 1; di++) { for(int dj = 0; dj <= 1; dj++) { if(i+di >= -1 && i+di < n && j+dj >= -1 && j+dj < m) { st.insert(mp(i+di,j+dj)); } } } for(auto x : st) { construct(x.fr,x.sc,-1); } swap(col[a],col[b]); swap(row[a],row[b]); grid[row[a]][col[a]] = a; grid[row[b]][col[b]] = b; for(auto x : st) { construct(x.fr,x.sc,+1); } return trq[1]; }
#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...