제출 #622286

#제출 시각아이디문제언어결과실행 시간메모리
622286Jomnoi자리 배치 (IOI18_seats)C++17
0 / 100
4049 ms63536 KiB
#include <bits/stdc++.h> #include "seats.h" using namespace std; const int MAX_N = 1e6 + 5; int H, W; vector<int> R, C; int tree[4 * MAX_N]; struct State { int minR, maxR, minC, maxC; }state[MAX_N]; void update(int idx, int l, int r, int q, int v) { if(l == r) { tree[idx] = v; return; } int mid = (l + r) / 2; if(q <= mid) { update(idx * 2, l, mid, q, v); } else { update(idx * 2 + 1, mid + 1, r, q, v); } tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]; } void give_initial_chart(int h, int w, vector <int> r, vector <int> c) { H = h, W = w, R = r, C = c; int minR = H - 1, maxR = 0, minC = W - 1, maxC = 0; for(int i = 0; i < H * W; i++) { minR = min(minR, R[i]); maxR = max(maxR, R[i]); minC = min(minC, C[i]); maxC = max(maxC, C[i]); state[i] = {minR, maxR, minC, maxC}; update(1, 0, H * W - 1, i, (maxR - minR + 1) * (maxC - minC + 1) == i + 1); } } int swap_seats(int a, int b) { if(a > b) { swap(a, b); } swap(R[a], R[b]), swap(C[a], C[b]); int minR = H - 1, maxR = 0, minC = W - 1, maxC = 0; if(a > 0) { minR = state[a - 1].minR; maxR = state[a - 1].maxR; minC = state[a - 1].minC; maxC = state[a - 1].maxC; } for(int i = a; i <= b; i++) { minR = min(minR, R[i]); maxR = max(maxR, R[i]); minC = min(minC, C[i]); maxC = max(maxC, C[i]); update(1, 0, H * W - 1, i, (maxR - minR + 1) * (maxC - minC + 1) == i + 1); } return tree[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...