이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "seats.h"
#include <cassert>
#include <map>
using namespace std;
constexpr int BLOCK = 2048; // TODO 1024
constexpr int INF = 1e9;
int n_blocks;
vector<int> v, prefMax, prefMin, suffAns;
// for each block
vector<map<int, vector<int>>> needMinFix, needMaxFix;
void compute(int block_i) {
const int begin = block_i*BLOCK, end = begin+BLOCK;
prefMax[begin] = v[begin];
prefMin[begin] = v[begin];
for (int i = begin+1; i < end; i++) {
prefMax[i] = max(prefMax[i-1], v[i]);
prefMin[i] = min(prefMin[i-1], v[i]);
}
needMinFix[block_i].clear();
needMaxFix[block_i].clear();
// Compute ans and need
for (int i = begin; i < end; i++) {
suffAns[i] = prefMax[i] - prefMin[i] == i;
needMinFix[block_i][prefMax[i] - i].push_back(i);
needMaxFix[block_i][prefMin[i] + i].push_back(i);
}
for (int i = end-2; i >= begin; i--) {
suffAns[i] += suffAns[i+1];
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
assert(H == 1);
n_blocks = (W + BLOCK-1) / BLOCK;
::v = C;
v.resize(n_blocks*BLOCK, INF);
prefMax.resize(n_blocks*BLOCK);
prefMin.resize(n_blocks*BLOCK);
suffAns.resize(n_blocks*BLOCK);
needMinFix.resize(n_blocks);
needMaxFix.resize(n_blocks);
for (int i = 0; i < n_blocks; i++) compute(i);
}
int countRange(vector<int> v, int l, int r) {
return lower_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
}
int swap_seats(int a, int b) {
// update in O(BLOCK log BLOCK)
swap(v[a], v[b]);
compute(a / BLOCK);
compute(b / BLOCK);
// query in O(W/BLOCK log BLOCK)
int currMX = -1, currMN = INF, ans = 0;
for (int i = 0; i < n_blocks; i++) {
const int start = i*BLOCK, end = start+BLOCK;
int low, high;
// nextMX
low = start-1, high = end;
while (low+1 < high) {
int mid = (low+high)/2;
if (prefMax[mid] < currMX) low = mid;
else high = mid;
}
const int nextMX = low+1;
// nextMN
low = start-1, high = end;
while (low+1 < high) {
int mid = (low+high)/2;
if (prefMin[mid] > currMN) low = mid;
else high = mid;
}
const int nextMN = low+1;
if (start <= currMX - currMN && currMX - currMN < min(nextMX, nextMN)) ans++;
if (nextMX < nextMN) {
ans += countRange(needMinFix[i][currMN], nextMX, nextMN);
} else if (nextMN < end) {
ans += countRange(needMaxFix[i][currMX], nextMN, nextMX);
}
if (max(nextMN, nextMX) < end) ans += suffAns[max(nextMN, nextMX)];
currMN = min(currMN, prefMin[end-1]);
currMX = max(currMX, prefMax[end-1]);
}
// ans++; // total match??
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |