이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll
const int N = 1e6 + 5;
const int inf = 1e9 + 7;
struct ST{
vector<int> Min, Max;
int N;
ST(int N): N(N){
Min.resize(N << 2);
Max.resize(N << 2);
}
void set(int i, int v, int lx, int rx, int x){
if(lx == rx) { Min[x] = Max[x] = v; return; }
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
}
void set(int i, int v){
set(i, v, 0, N, 1);
}
int getmax(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return Max[x];
int m = (lx + rx) >> 1;
return max(getmax(l, r, lx, m, x << 1), getmax(l, r, m + 1, rx, x << 1 | 1));
}
int getmax(int l, int r){
return getmax(l, r, 0, N, 1);
}
int getmin(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return inf;
if(lx >= l && rx <= r) return Min[x];
int m = (lx + rx) >> 1;
return min(getmin(l, r, lx, m, x << 1), getmin(l, r, m + 1, rx, x << 1 | 1));
}
int getmin(int l, int r){
return getmin(l, r, 0, N, 1);
}
}X(N), Y(N);
int cnt;
bool is;
vector<int> mnx, mxx, mny, mxy;
vector<int> x, y;
bool check(int i){
if((mxx[i] - mnx[i] + 1) * (mxy[i] - mny[i] + 1) == i + 1){
return true;
}
return false;
}
void give_initial_chart(int n, int m, vector<int> r, vector<int> c) {
int sz = n * m;
mnx.resize(sz);
mxx.resize(sz);
mny.resize(sz);
mxy.resize(sz);
swap(x, r);
swap(y, c);
cnt = 0;
for(int i=0;i<sz;i++){
mnx[i] = mxx[i] = x[i];
mny[i] = mxy[i] = y[i];
if(i){
mnx[i] = min(mnx[i], mnx[i - 1]);
mny[i] = min(mny[i], mny[i - 1]);
mxx[i] = max(mxx[i], mxx[i - 1]);
mxy[i] = max(mxy[i], mxy[i - 1]);
}
if(check(i)) cnt++;
}
is = 0;
if(max(n, m) <= 1000){
is = 1;
}
for(int i=0;i<sz;i++){
X.set(i, x[i]);
Y.set(i, y[i]);
}
}
//~ int ans(int i, int j){
//~ X.set(i, x[i]), Y.set(i, y[i]);
//~ X.set(j, x[j]), Y.set(j, y[j]);
//~ }
int swap_seats(int i, int j){
swap(x[i], x[j]);
swap(y[i], y[j]);
//~ if(is){
//~ return ans(i, j);
//~ }
for(int k=i;k<=j;k++){
if(check(k)) cnt--;
mnx[k] = mxx[k] = x[k];
mny[k] = mxy[k] = y[k];
if(k){
mnx[k] = min(mnx[k], mnx[k - 1]);
mny[k] = min(mny[k], mny[k - 1]);
mxx[k] = max(mxx[k], mxx[k - 1]);
mxy[k] = max(mxy[k], mxy[k - 1]);
}
if(check(k)) cnt++;
}
return cnt;
}
# | 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... |