제출 #115544

#제출 시각아이디문제언어결과실행 시간메모리
115544WhipppedCream자리 배치 (IOI18_seats)C++17
17 / 100
4104 ms44920 KiB
#include <bits/stdc++.h> #include "seats.h" #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; const int maxn = 1e6+5; int r[maxn], c[maxn]; int mnr[maxn]; int mxr[maxn]; int mnc[maxn]; int mxc[maxn]; int n, m; int ans = 0; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { n = H; m = W; for(int i = 0; i< n*m; i++) { r[i] = R[i]; c[i] = C[i]; } for(int i = 0; i< n*m; i++) { mnr[i] = min(i?mnr[i-1]:n*m, r[i]); mxr[i] = max(i?mxr[i-1]:0, r[i]); mnc[i] = min(i?mnc[i-1]:n*m, c[i]); mxc[i] = max(i?mxc[i-1]:0, c[i]); if((mxr[i]-mnr[i]+1)*(mxc[i]-mnc[i]+1) == i+1) ans++; } } int swap_seats(int a, int b) { if(a> b) swap(a, b); swap(r[a], r[b]); swap(c[a], c[b]); for(int i = a; i< b; i++) { int old = 0; if((mxr[i]-mnr[i]+1)*(mxc[i]-mnc[i]+1) == i+1) old = 1; mnr[i] = min(i?mnr[i-1]:n*m, r[i]); mxr[i] = max(i?mxr[i-1]:0, r[i]); mnc[i] = min(i?mnc[i-1]:n*m, c[i]); mxc[i] = max(i?mxc[i-1]:0, c[i]); int nw = 0; if((mxr[i]-mnr[i]+1)*(mxc[i]-mnc[i]+1) == i+1) nw = 1; ans += nw-old; } 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...