제출 #434034

#제출 시각아이디문제언어결과실행 시간메모리
434034frodakcin자리 배치 (IOI18_seats)C++11
17 / 100
4050 ms55492 KiB
#include "seats.h" #include <algorithm> template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;} template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;} const int INF = 0x3f3f3f3f; int N, ans; std::vector<int> R, C; //ST 1, 2, 4 std::vector<int> maxr, minr, maxc, minc; int calc(int u, int v) { for(int i=u;i<v;++i) if(i+1 == (maxr[i+1]-minr[i+1])*(maxc[i+1]-minc[i+1])) --ans; for(int i=u;i<v;++i) { minr[i+1]=std::min(minr[i], R[i]); maxr[i+1]=std::max(maxr[i], R[i]+1); minc[i+1]=std::min(minc[i], C[i]); maxc[i+1]=std::max(maxc[i], C[i]+1); if(i+1 == (maxr[i+1]-minr[i+1])*(maxc[i+1]-minc[i+1])) ++ans; } return ans; } void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) { R=_R, C=_C; N = H*W; maxr.assign(N+1, -1); maxc.assign(N+1, -1); minr.assign(N+1, INF); minc.assign(N+1, INF); calc(0, N); } int swap_seats(int a, int b) { std::swap(R[a], R[b]); std::swap(C[a], C[b]); if(b<a) std::swap(a,b); return calc(a, b+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...