제출 #1208380

#제출 시각아이디문제언어결과실행 시간메모리
1208380Aviansh자리 배치 (IOI18_seats)C++20
0 / 100
4091 ms39472 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; vector<int> r; vector<int> c; vector<int>prefmnr; vector<int>prefmxr; vector<int>prefmnc; vector<int>prefmxc; int ans; void give_initial_chart(int h, int w, vector<int> R, vector<int> C) { r = R; c = C; prefmnr = vector<int>(h*w,-1); prefmxr = vector<int>(h*w,-1); prefmnc = vector<int>(h*w,-1); prefmxc = vector<int>(h*w,-1); ans=0; int mnr = r[0]; int mxr = r[0]; int mnc = c[0]; int mxc = c[0]; for(int i = 0;i<h*w;i++){ mnr=min(mnr,r[i]); mxr=max(mxr,r[i]); mnc=min(mnc,c[i]); mxc=max(mxc,c[i]); prefmnr[i]=mnr; prefmxr[i]=mxr; prefmnc[i]=mnc; prefmxc[i]=mxc; bool val = ((i+1)==((mxr-mnr+1)*(mxc-mnc+1))); ans+=val; } } int swap_seats(int a, int b) { int ans2=0; int mnr = r[0]; int mxr = r[0]; int mnc = c[0]; int mxc = c[0]; for(int i = 0;i<r.size();i++){ mnr=min(mnr,r[i]); mxr=max(mxr,r[i]); mnc=min(mnc,c[i]); mxc=max(mxc,c[i]); if(i>=a&&i<=b) continue; bool val = ((i+1)==((mxr-mnr+1)*(mxc-mnc+1))); ans2+=val; } for(int i = a;i<=b;i++){ int mnr = prefmnr[i]; int mxr = prefmxr[i]; int mnc = prefmnc[i]; int mxc = prefmxc[i]; bool val = ((i+1)==((mxr-mnr+1)*(mxc-mnc+1))); ans-=val; } assert(ans==ans2); swap(r[a],r[b]); swap(c[a],c[b]); prefmnr[0]=r[0]; prefmxr[0]=r[0]; prefmnc[0]=c[0]; prefmxc[0]=c[0]; for(int i = a;i<=b;i++){ if(i){ prefmnr[i]=min(r[i],prefmnr[i-1]); prefmxr[i]=max(r[i],prefmxr[i-1]); prefmnc[i]=min(c[i],prefmnc[i-1]); prefmxc[i]=max(c[i],prefmxc[i-1]); } } for(int i = a;i<=b;i++){ int mnr = prefmnr[i]; int mxr = prefmxr[i]; int mnc = prefmnc[i]; int mxc = prefmxc[i]; bool val = ((i+1)==((mxr-mnr+1)*(mxc-mnc+1))); ans+=val; } 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...